home *** CD-ROM | disk | FTP | other *** search
/ ftp.parl.clemson.edu / 2015-02-07.ftp.parl.clemson.edu.tar / ftp.parl.clemson.edu / pub / pvfs2 / orangefs-2.8.3-20110323.tar.gz / orangefs-2.8.3-20110323.tar / orangefs / src / io / description / dist-twod-stripe.c < prev    next >
C/C++ Source or Header  |  2010-12-21  |  19KB  |  576 lines
  1. /*
  2.  * (C) Kyle Schochenmaier 2007
  3.  * two-dimensional distribution
  4.  *
  5.  * See COPYING in top-level directory.
  6.  */
  7. /* twod-stripe will take all of the servers in the filesystem and
  8.  * partition them into num_groups groups.  Data will then be striped to
  9.  * each group before we move onto the next group.  The strip_factor will
  10.  * determine how many chunks of strip_size are written to each server
  11.  * in each group before we transition to the next group.
  12.  * The striping on the group level is done round-robin in the same
  13.  * fashion as simple-stripe
  14.  */
  15.  
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18. #include <string.h>
  19.  
  20. #define __PINT_REQPROTO_ENCODE_FUNCS_C
  21. #include "pvfs2-encode-stubs.h"
  22. #include "pint-distribution.h"
  23. #include "pvfs2-types.h"
  24. #include "pvfs2-dist-twod-stripe.h"
  25. #include "pvfs2-util.h"
  26. #include "gossip.h"
  27. #include "pint-dist-utils.h"
  28. #include "pvfs2-internal.h"
  29.  
  30. #include <assert.h>
  31.  
  32. /*
  33.  * If server_ct and num_groups dont play nicely, we will have one (the last) 
  34.  * set of servers that will contain anywhere between <n+1...n*2-1> servers.
  35.  * Since we base the dist on the number of servers, we will have to provide
  36.  * more space on the last set than the other sets to keep load balanced.
  37.  */
  38.  
  39. static PVFS_offset logical_to_physical_offset(void* params,
  40.                                               PINT_request_file_data* fd,
  41.                                               PVFS_offset logical_offset)
  42. {
  43.     PVFS_offset ret_offset = 0;    /* ret value */
  44.  
  45.     uint32_t server_nr = fd->server_nr;
  46.     uint32_t server_ct = fd->server_ct;
  47.     uint32_t group_nr = 0;        /* group server_nr is in */
  48.     uint32_t servers_in_group = 0;  /* # servers in group_nr */
  49.     uint32_t gserver_nr = 0;        /* server_nr relative to group */
  50.     uint32_t factor;
  51.     uint32_t num_groups;
  52.     uint32_t small_group_size;
  53.     PVFS_size global_stripe_size;
  54.     PVFS_size global_stripes;
  55.     PVFS_size group_stripes;
  56.     PVFS_size group_strips;
  57.     PVFS_offset last_stripe_offset; /* offset into a stripe */
  58.     PVFS_offset group_offset;   /* offset into groups */
  59.     PVFS_offset local_offset;   /* offset inside a group */
  60.     PVFS_twod_stripe_params* dparam;
  61.     PVFS_size strip_size;
  62.  
  63.     if(logical_offset==0)
  64.     {
  65.         return 0;
  66.     }
  67.  
  68.     /* param related variables */
  69.     dparam = (PVFS_twod_stripe_params*)params;
  70.     factor = dparam->group_strip_factor;
  71.     num_groups = dparam->num_groups;
  72.     strip_size = dparam->strip_size;
  73.  
  74.     if( num_groups == 0 || server_ct == 0 )
  75.     {
  76.         gossip_err("%s: Invalid num_groups/server_ct options: "
  77.                    "gr:%d server:%d\n",
  78.                    __func__, num_groups, server_ct);
  79.     }
  80.  
  81.     if(num_groups > server_ct )
  82.         num_groups = server_ct;
  83.  
  84.     /* size of all groups that are of equal size: all groups
  85.      * except when server_ct doesnt divide evenly into num_groups */
  86.     small_group_size = server_ct / num_groups;
  87.  
  88.     /* global variables, which describe the entire dist reg. of groups */
  89.     global_stripe_size = server_ct * strip_size * factor;
  90.  
  91.     /* for future use, determine the layout of the system */
  92.     /* group that server_nr is in: */
  93.     if(server_nr >= (num_groups-1)*(small_group_size))
  94.     {
  95.         group_nr = num_groups-1;    /* in last group */
  96.     }
  97.     else
  98.     {
  99.         group_nr = server_nr/small_group_size;  /* generic size */
  100.     }
  101.  
  102.     if(group_nr == num_groups-1)
  103.     {
  104.         servers_in_group = server_ct - (num_groups-1)*(small_group_size);
  105.     }
  106.     else
  107.     {
  108.         servers_in_group = small_group_size;
  109.     }
  110.  
  111.     /* calculate the number of full stripes across all groups */
  112.     global_stripes = logical_offset / global_stripe_size;
  113.  
  114.     /* calculate offset into the last global stripe (first not full stripe) */
  115.     last_stripe_offset = logical_offset - global_stripes * global_stripe_size;
  116.  
  117.     /* get all of the blocks already accounted for via global stripes */
  118.     ret_offset += global_stripes * factor * strip_size;
  119.  
  120.     /* find out if logical offset falls inside or before this group_nr */
  121.  
  122.     /* is the offset at least in this group?
  123.      * if so, we need to add more to the ret_offset */
  124.     group_offset = last_stripe_offset -
  125.         group_nr * factor * strip_size * small_group_size;
  126.  
  127.     local_offset = group_offset - 
  128.         ( servers_in_group * factor * strip_size );
  129.  
  130.     gserver_nr = server_nr - group_nr * small_group_size; 
  131.  
  132.     /* is the offset in this group? */
  133.     if(group_offset > 0)
  134.     {
  135.         if(local_offset > 0)
  136.         {   /* no, l_off is in a group > group_nr, get as close as possible */
  137.             ret_offset += factor * strip_size;
  138.         }
  139.         else
  140.         {   /* l_off is in this group, calculate the offset now */
  141.             /* find out if l_off ends on this server */
  142.             group_stripes = group_offset / (servers_in_group * strip_size );
  143.             /* add the stripes to the offset calc */
  144.             ret_offset += group_stripes * strip_size;
  145.             /* get rid of full group stripes */
  146.             group_offset -= group_stripes * strip_size * servers_in_group;
  147.             group_strips = group_offset / strip_size;
  148.             /* if the # of strips >= server_nr+1, this server strip is full */
  149.             if(group_strips >= gserver_nr+1)
  150.                 ret_offset+=strip_size;
  151.             else if(group_strips == gserver_nr)    /* not on this server */
  152.                     ret_offset += group_offset % strip_size;
  153.         }
  154.     }
  155.     /* else, l_off is in a server in group < group_nr */
  156.     /* return the end of the last global stripe then */
  157.  
  158.     gossip_debug(GOSSIP_DIST_DEBUG,
  159.                  "%s: server_nr: %d l_off: %llu p_off: %llu\n",
  160.                  __func__,
  161.                  fd->server_nr,
  162.                  llu(logical_offset),
  163.                  llu(ret_offset));
  164.     return ret_offset;
  165. }
  166.  
  167. /* 
  168.  * For any block (block_nr) in a given group (group_nr) on any
  169.  * server (server_nr), the following will always remain true:
  170.  * 1.  All blocks in the same group and same strip with server<server_nr
  171.  *     will always be full.
  172.  * 2.  All blocks in all groups<group_nr in the same global_stripe (gstripe_nr)
  173.  *     are full.
  174.  * 3.  All blocks in all global_stripes < gstripe_nr are full.
  175.  */
  176. static PVFS_offset physical_to_logical_offset(void* params,
  177.                                               PINT_request_file_data* fd,
  178.                                               PVFS_offset physical_offset)
  179. {
  180.     PVFS_offset ret_offset = 0;
  181.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  182.     uint32_t server_nr = fd->server_nr;
  183.     uint32_t server_ct = fd->server_ct;
  184.     uint32_t group_nr = 0;
  185.     PVFS_size strip_size = dparam->strip_size;
  186.     PVFS_size strips = physical_offset / strip_size;
  187.     uint32_t servers_in_group = 0;
  188.     /* determine layout of system */
  189.     uint32_t small_group_size = server_ct / dparam->num_groups;
  190.     uint32_t gserver_nr = 0;
  191.     uint32_t factor = dparam->group_strip_factor;
  192.     PVFS_size full_group_strips = strips % factor;
  193.     PVFS_size global_stripes = 0;
  194.     uint32_t num_groups = dparam->num_groups;
  195.  
  196.     if( num_groups == 0 || server_ct == 0 )
  197.     {
  198.         gossip_err(
  199.             "%s: Invalid num_groups/server_ct options: "
  200.             "gr:%d server:%d\n",
  201.             __func__,num_groups,server_ct);
  202.     }
  203.  
  204.     if(num_groups > server_ct)
  205.         num_groups = server_ct;
  206.     
  207.     /* if we are a server in the last group, make sure things are happy */
  208.     if(server_nr >= (num_groups-1)*(small_group_size))
  209.     {
  210.         group_nr = num_groups-1;
  211.     }
  212.     else
  213.     {
  214.         group_nr = server_nr/small_group_size;
  215.     }
  216.  
  217.     /* if we're in the last group, make sure we have the correct size! */
  218.     if(group_nr == num_groups-1)
  219.     {
  220.         servers_in_group = server_ct - (num_groups-1)*(small_group_size);
  221.     }
  222.     else
  223.     {
  224.         servers_in_group = small_group_size;
  225.     }
  226.  
  227.     /* find the server_nr relative to the group it is in */
  228.     gserver_nr = server_nr - group_nr * small_group_size;
  229.  
  230.     /* 
  231.      * if(#strips >= factor) we have at least one full stripe
  232.      * else nothing more is filled
  233.      */
  234.     if(strips>factor)
  235.     {
  236.         global_stripes = strips/factor;
  237.         ret_offset += global_stripes * factor * server_ct * strip_size;
  238.     }
  239.     else if(strips==factor)  /* we're perfectly aligned with a strip */
  240.     {
  241.             ret_offset += strips * server_ct * strip_size;
  242.     }
  243.  
  244.     /* Add all the servers in groups lower than current group */
  245.     ret_offset += group_nr * small_group_size * factor * strip_size;
  246.  
  247.     /* Add all group strips */
  248.     ret_offset += full_group_strips * servers_in_group * strip_size;
  249.  
  250.     /* Add all servers in group in this strip */
  251.     ret_offset += gserver_nr * strip_size;
  252.  
  253.     /* Add the final portion of the physical strip */
  254.     ret_offset += physical_offset % strip_size;
  255.  
  256.     gossip_debug(GOSSIP_DIST_DEBUG,
  257.                  "%s: server_nr: %d p_off: %llu l_off: %llu\n",
  258.                  __func__,
  259.                  fd->server_nr,
  260.                  llu(physical_offset),
  261.                  llu(ret_offset));
  262.     return ret_offset;
  263. }
  264.  
  265. static PVFS_size logical_file_size(void* params,
  266.                                    uint32_t server_ct,
  267.                                    PVFS_size *psizes)
  268. {
  269.     PVFS_size cur_max = 0;
  270.     int i = 0;
  271.     /* generic fd request so we can cheat and use p_to_l */
  272.     if(!psizes)
  273.     {
  274.         return -1;
  275.     }
  276.  
  277.     for(i = 0; i < server_ct; i++)
  278.     {
  279.         if(psizes[i])
  280.             cur_max+=psizes[i];
  281.     }
  282.  
  283.     gossip_debug(GOSSIP_DIST_DEBUG,
  284.                  "%s: server_ct: %u log_size: %llu\n",
  285.                  __func__,
  286.                  server_ct,
  287.                  llu(cur_max));
  288.  
  289.     return cur_max;
  290. }
  291.  
  292. /* Given a logical offset, return the next offset which is directly
  293.  * mapped to a physical address on this server.
  294.  *
  295.  * NOTE:
  296.  * For all server's that are in a group before server_nr, we will
  297.  * find the physical address of the last strip, add one, and then
  298.  * return the physical_to_logical() mapping to it.
  299.  */
  300.  
  301. static PVFS_offset next_mapped_offset(void* params,
  302.                                       PINT_request_file_data* fd,
  303.                                       PVFS_offset logical_offset)
  304. {
  305.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  306.     uint32_t server_nr = fd->server_nr;
  307.     uint32_t server_ct = fd->server_ct;
  308.     PVFS_size strip_size = dparam->strip_size;
  309.     uint32_t num_groups = dparam->num_groups;
  310.     uint32_t small_group_size = server_ct / num_groups;
  311.     uint32_t factor = dparam->group_strip_factor;
  312.     uint32_t group_nr = 0;
  313.     uint32_t gserver_nr = 0;
  314.     PVFS_size global_stripe_size = server_ct * factor * strip_size;
  315.     uint32_t global_stripes = logical_offset / global_stripe_size;
  316.     PVFS_size small_group_stripe = small_group_size * factor * strip_size;
  317.     PVFS_size cur_group_size = 0;
  318.  
  319.     uint32_t servers_in_group = 0;
  320.     PVFS_offset l_off = logical_offset - global_stripe_size * global_stripes;
  321.     PVFS_offset p_off = 0;
  322.     PVFS_offset g_off = 0;
  323.     uint32_t g_strips = 0;
  324.     /* we'll find the server where teh logical offset should be, then
  325.      * use that to compute the address offsets for everyone else.
  326.      */
  327.     uint32_t total_stripes = 0;
  328.  
  329.     gossip_debug(GOSSIP_DIST_DEBUG,
  330.                  "%s: fsize: %llu l_off: %llu server_nr: "
  331.                  "%d server_ct: %d\n\t",
  332.                  __func__,
  333.                  llu(fd->fsize),
  334.                  llu(logical_offset),
  335.                  fd->server_nr,
  336.                  fd->server_ct);
  337.  
  338.     if(logical_offset == 0)
  339.     {
  340.         return physical_to_logical_offset(params,fd,0);
  341.     }
  342.  
  343.     if( num_groups == 0 || server_ct == 0 )
  344.     {
  345.         gossip_err("%s: Invalid num_groups/server_ct options: "
  346.                    "gr:%d server:%d\n",
  347.                    __func__,
  348.                    num_groups,
  349.                    server_ct);
  350.     }
  351.     if(num_groups > server_ct)
  352.         num_groups = server_ct;
  353.     total_stripes += global_stripes * factor;
  354.  
  355.     /* if we are a server in the last group, make sure things are happy */
  356.     if(server_nr >= (num_groups-1)*(small_group_size))
  357.         group_nr = num_groups-1;
  358.     else
  359.         group_nr = server_nr/small_group_size;
  360.     if(group_nr == num_groups-1)
  361.         servers_in_group = server_ct - (num_groups-1)*(small_group_size);
  362.     else
  363.         servers_in_group = small_group_size;
  364.     gserver_nr = server_nr - group_nr * small_group_size;
  365.  
  366.     cur_group_size = servers_in_group * factor * strip_size;
  367.  
  368.     /* Find the server where the l_off should be: */
  369.  
  370.     /* if the logical offset ends on a group > group_nr, 
  371.      * we are guaranteed to have filled this stripe, add a stripe
  372.      * and calculate the logical offset based on the physical off
  373.      */
  374.     /* is server_nr in a group < l_off's group? */
  375.     if(l_off >= (group_nr)*small_group_stripe+cur_group_size)
  376.     {
  377.         total_stripes += factor;
  378.         p_off += total_stripes * strip_size;
  379.         return physical_to_logical_offset(params,fd,p_off);
  380.     }
  381.     else    /* check to see if we're already passed the l_off */
  382.     {
  383.         if((l_off < (group_nr)*small_group_stripe+cur_group_size) &&
  384.            (l_off > group_nr*small_group_stripe))
  385.         {
  386.             /* logical_offset ends on this group, find the server! */
  387.             g_off = l_off - group_nr*small_group_stripe;
  388.             g_strips = g_off / (servers_in_group * strip_size);
  389.             total_stripes += g_strips;
  390.             g_off -= g_strips * strip_size * servers_in_group;
  391.  
  392.             /* does logical_offset land on a server after server_nr? */
  393.             if(g_off < gserver_nr*strip_size)
  394.             {
  395.                 p_off += (total_stripes) * strip_size;
  396.                 return physical_to_logical_offset(params,fd,p_off);
  397.             }
  398.             else    /* is l_off on a larger# server? */
  399.                 if( g_off >= (gserver_nr+1) * strip_size)
  400.                 {
  401.                     p_off += (total_stripes+1) * strip_size;
  402.                     return physical_to_logical_offset(params,fd,p_off);
  403.                 }
  404.                 else
  405.                 {   /* We're on the correct server! */
  406.                     return logical_offset;
  407.                 }
  408.         }
  409.         else
  410.         {
  411.             /* We're beyond the logical offset, dont add anything */
  412.             p_off += total_stripes * strip_size;
  413.             return physical_to_logical_offset(params,fd,p_off);
  414.         }
  415.     }
  416. }
  417.  
  418.  
  419. /*
  420.  * Beginning in a given physical location, return the number of contiguous
  421.  * bytes in the physical bytes stream on the current PVFS server that map
  422.  * to contiguous bytes in the logical byte sequence.  Returns a length in
  423.  * bytes.
  424.  */
  425. static PVFS_size contiguous_length(void* params,
  426.                                    PINT_request_file_data* fd,
  427.                                    PVFS_offset physical_offset)
  428. {
  429.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  430.     return (dparam->strip_size - (physical_offset % dparam->strip_size));
  431. }
  432.  
  433.  
  434. static int set_param(const char* dist_name, void* params,
  435.                      const char* param_name, void* value)
  436. {
  437.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  438.     if(strcmp(param_name, "strip_size")==0)
  439.     {
  440.         if(*(PVFS_size*)value <=0)
  441.             gossip_err("ERROR: strip_size param <= 0!\n");
  442.         else
  443.         {
  444.             gossip_debug(GOSSIP_DIST_DEBUG,
  445.                          "%s: strip_size: %llu\n",__func__,
  446.                          llu(*(PVFS_size*)value));
  447.             memcpy(&(dparam->strip_size),value,sizeof(PVFS_size));
  448.         }
  449.     }
  450.     else if(strcmp(param_name, "num_groups")==0)
  451.     {
  452.         if(*(int64_t*)value <= 0)
  453.         {
  454.             gossip_err("ERROR: num_groups param <= 0!\n");
  455.         }
  456.         else
  457.         {
  458.             gossip_debug(GOSSIP_DIST_DEBUG,
  459.                          "%s: num_groups: %lld\n",
  460.                          __func__, lld(*(int64_t*)value));
  461.             dparam->num_groups = *(int64_t*)value;
  462.         }
  463.     }
  464.     else if(strcmp(param_name, "group_strip_factor")==0)
  465.     {
  466.         if(*(int64_t*)value <= 0)
  467.             gossip_err("ERROR: group_strip_factor param <= 0!\n");
  468.         else
  469.         {
  470.             gossip_debug(GOSSIP_DIST_DEBUG,
  471.                          "%s: group_strip_factor: %lld\n",
  472.                          __func__,lld(*(int64_t*)value));
  473.  
  474.             dparam->group_strip_factor = *(int64_t*)value;
  475.         }
  476.     }
  477.     else
  478.     {
  479.         return -PVFS_EINVAL;
  480.     }
  481.     return 0;
  482. }
  483.  
  484. static void encode_params(char **pptr, void* params)
  485. {
  486.     PVFS_twod_stripe_params *dparam =(PVFS_twod_stripe_params*)params;
  487.     encode_uint32_t(pptr,&dparam->num_groups);
  488.     encode_PVFS_size(pptr, &dparam->strip_size);
  489.     encode_uint32_t(pptr,&dparam->group_strip_factor);
  490. }
  491.  
  492.  
  493. static void decode_params(char **pptr, void* params)
  494. {
  495.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  496.     decode_uint32_t(pptr, &dparam->num_groups);
  497.     decode_PVFS_size(pptr, &dparam->strip_size);
  498.     decode_uint32_t(pptr, &dparam->group_strip_factor);
  499. }
  500.  
  501. static void registration_init(void* params)
  502. {
  503.     PINT_dist_register_param(PVFS_DIST_TWOD_STRIPE_NAME, "num_groups",
  504.                              PVFS_twod_stripe_params, num_groups);
  505.     PINT_dist_register_param(PVFS_DIST_TWOD_STRIPE_NAME, "strip_size",
  506.                              PVFS_twod_stripe_params, strip_size);
  507.     PINT_dist_register_param(PVFS_DIST_TWOD_STRIPE_NAME, "group_strip_factor",
  508.                              PVFS_twod_stripe_params, group_strip_factor);
  509. }
  510.  
  511. static void unregister(void)
  512. {
  513.     PINT_dist_unregister_param(PVFS_DIST_TWOD_STRIPE_NAME, "num_groups");
  514.     PINT_dist_unregister_param(PVFS_DIST_TWOD_STRIPE_NAME, "strip_size");
  515.     PINT_dist_unregister_param(PVFS_DIST_TWOD_STRIPE_NAME, 
  516.                                "group_strip_factor");
  517. }
  518.  
  519. static char *params_string(void *params)
  520. {
  521.     char param_string[1024];
  522.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  523.  
  524.     sprintf(param_string, "num_groups:%d,strip_size:%llu,factor:%d\n",
  525.             dparam->num_groups, llu(dparam->strip_size), dparam->group_strip_factor);
  526.     return strdup(param_string);
  527. }
  528.  
  529. static PVFS_size get_blksize(void* params)
  530. {
  531.     PVFS_twod_stripe_params* dparam = (PVFS_twod_stripe_params*)params;
  532.     /* report the strip size as the block size */
  533.     return(dparam->strip_size);
  534. }
  535.  
  536. /* default twod_stripe_params */
  537. static PVFS_twod_stripe_params twod_stripe_params = {
  538.     PVFS_DIST_TWOD_STRIPE_DEFAULT_GROUPS,   /* num_groups */
  539.     PVFS_DIST_TWOD_STRIPE_DEFAULT_STRIP_SIZE,
  540.     PVFS_DIST_TWOD_STRIPE_DEFAULT_FACTOR
  541. };
  542.  
  543. static PINT_dist_methods twod_stripe_methods = {
  544.     logical_to_physical_offset,
  545.     physical_to_logical_offset,
  546.     next_mapped_offset,
  547.     contiguous_length,
  548.     logical_file_size,
  549.     PINT_dist_default_get_num_dfiles,
  550.     set_param,
  551.     get_blksize,
  552.     encode_params,
  553.     decode_params,
  554.     registration_init,
  555.     unregister,
  556.     params_string
  557. };
  558.  
  559. PINT_dist twod_stripe_dist = {
  560.     .dist_name = PVFS_DIST_TWOD_STRIPE_NAME,
  561.     .name_size = roundup8(PVFS_DIST_TWOD_STRIPE_NAME_SIZE), /* name size */
  562.     .param_size = roundup8(sizeof(PVFS_twod_stripe_params)), /* param size */
  563.     .params = &twod_stripe_params,
  564.     .methods = &twod_stripe_methods
  565. };
  566.  
  567. /*
  568.  * Local variables:
  569.  *  mode: c
  570.  *  c-indent-level: 4
  571.  *  c-basic-offset: 4
  572.  * End:
  573.  *
  574.  * vim: ft=c ts=8 sts=4 sw=4 expandtab
  575.  */
  576.