home *** CD-ROM | disk | FTP | other *** search
/ PC Plus SuperCD (UK) 1999 May / pcp151c.iso / misc / src / install / libfdisk / alloc.c next >
Encoding:
C/C++ Source or Header  |  1998-09-13  |  41.1 KB  |  1,282 lines
  1. /* handles automatic allocation of space for requested new partitions */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <unistd.h>
  6. #include <malloc.h>
  7. #include <string.h>
  8.  
  9. #include "libfdisk.h"
  10.  
  11.  
  12. /* these routines manipulate a space map - can be used or free space */
  13. /* the space map is a array of structures, each structure indicating */
  14. /* the start and size of a chunk of  space */
  15. /* if the size is 0, then it is an UNUSED entry in the free space table */
  16.  
  17. /* initialze a space map data type */
  18. int fdiskSpaceMapInit( SpaceMap **map ) {
  19.     *map = (SpaceMap *) malloc( sizeof(SpaceMap) );
  20.     (*map)->len = 0;
  21.     (*map)->num = 0;
  22.     (*map)->entry = NULL;
  23.     return FDISK_SUCCESS;
  24. }
  25.  
  26. /* reduce # entries to smallest possible number by combining */
  27. /* touching/overlapping entries                              */
  28. /* fuzz introduced because can't allocate space in less than */
  29. /* that size chunk ususally                                  */
  30. int fdiskSpaceMapKrunch( SpaceMap *map, unsigned int fuzz ) {
  31.     unsigned int start;
  32.     unsigned int end;
  33.     unsigned int maxend;
  34.     unsigned int tmpend;
  35.     unsigned int i, j;
  36.     
  37.     for (i=0; i < map->num-1; ) {
  38.  
  39.     start  = map->entry[i].start;
  40.     end    = start + map->entry[i].size;
  41.     maxend = end;
  42.  
  43.     /* see if next partition can merge with existing */
  44.     if (map->entry[i+1].start <= end+fuzz) {
  45.         /* find last space which starts inside existing space */
  46.         for (j=i+1; j < map->num; )
  47.         if (map->entry[j].start <= end+fuzz) {
  48.             tmpend=map->entry[j].start+map->entry[j].size;
  49.             if (tmpend > maxend)
  50.             maxend = tmpend;
  51.             
  52.             fdiskSpaceMapDel( map, j );
  53.             continue;
  54.         } else
  55.             break;
  56.  
  57.         /* adjust first space to contain all */
  58.         map->entry[i].size = maxend - map->entry[i].start;
  59.     } else {
  60.         /* move to the next entry and keep going */
  61.         i++;
  62.     }
  63.     }
  64.     
  65.     return FDISK_SUCCESS;
  66. }
  67.  
  68. /* add an entry to a map */
  69. /* fuzz is the smallest chunk we can allocate, used to close up holes */
  70. /* in the space map which are not usable                              */
  71. int fdiskSpaceMapAdd( SpaceMap *map, SpaceMapEntry *entry, unsigned int fuzz ){
  72.     int i;
  73.     int spot;
  74.     int num, len;
  75.  
  76.     /* see if anything exists yet */
  77.     if (map->entry) {
  78.     /* we want to keep map space sorted by start */
  79.     num = map->num;
  80.     len = map->len;
  81.     if (num == 0) {
  82.         spot = -1;
  83.     } else if (entry->start < map->entry[0].start) {
  84.         spot = -1;
  85.     } else if (entry->start > map->entry[num-1].start) {
  86.         spot = num;
  87.     } else {
  88.         /* NEW CODE (Nov 7 1997) WATCH CLOSELY! */
  89.         for (spot=0; spot < num-1; spot++)
  90.         if (entry->start >= map->entry[spot].start &&
  91.             entry->start <= map->entry[spot+1].start)
  92.             break;
  93.     }
  94.     } else {
  95.     /* new list */
  96.     num = 0;
  97.     len = 0;
  98.     spot = -1;
  99.     }
  100.  
  101.     /* are we simply adjusting an existing chunk, or creating a new one ? */
  102.     /* if its a new entry at end of list we skip this check altogether    */
  103.     if (spot > -1 && spot != num && entry->start == map->entry[spot].start){
  104.     /* editting existing entry */
  105.     if (entry->size > map->entry[spot].size)
  106.         map->entry[spot].size = entry->size;
  107.     } else {
  108.         /* insert into list */
  109.     map->num++;
  110.     if (map->num > len) {
  111.         len += SpaceMapChunk;
  112.         map->len = len;
  113.         map->entry = (SpaceMapEntry *) realloc(map->entry,
  114.                            len*sizeof(SpaceMapEntry));
  115.         memset(&map->entry[map->num-1], 0, len*sizeof(SpaceMapEntry));
  116.     }
  117.     
  118.     for (i=map->num-1; i >= 0 && i > spot; i--)
  119.         memcpy(&map->entry[i], &map->entry[i-1], sizeof(SpaceMapEntry));
  120.  
  121.     if (spot != num)
  122.         memcpy(&map->entry[spot+1], entry, sizeof(SpaceMapEntry));
  123.     else
  124.         memcpy(&map->entry[spot], entry, sizeof(SpaceMapEntry));
  125.     }
  126.  
  127.     /* go thru and consolidate to smallest set of entries          */
  128.     /* for now lets not use fuzz, as it erases spaces where we may */
  129.     /* actually want to put an EPT, for example                    */
  130.     /* fdiskSpaceMapKrunch( map, fuzz );                           */
  131.     fdiskSpaceMapKrunch( map, 0 );
  132.     
  133.     return FDISK_SUCCESS;
  134. }
  135.  
  136.  
  137. /* delete an entry from a map, index by position in list */
  138. int fdiskSpaceMapDel( SpaceMap *map, unsigned int n ) {
  139.     int i;
  140.  
  141.     /* see if anything exists yet */
  142.     if (!map->entry || n < 0 || n > map->num-1)
  143.     return FDISK_ERR_BADNUM;
  144.  
  145.     for (i=n; i<map->num-1; i++)
  146.     memcpy(&map->entry[i], &map->entry[i+1], sizeof(SpaceMapEntry));
  147.  
  148.     memset(&map->entry[map->num-1], 0, sizeof(SpaceMapEntry));
  149.     map->num--;
  150.     return FDISK_SUCCESS;
  151. }
  152.  
  153.  
  154. int fdiskSpaceMapFree( SpaceMap *map ) {
  155.  
  156.     if (!map)
  157.     return FDISK_ERR_BADPTR;
  158.  
  159.     if (map->entry)
  160.     free(map->entry);
  161.  
  162.     free(map);
  163.     return FDISK_SUCCESS;
  164. }
  165.  
  166.         
  167.  
  168. /*                                                                        */
  169. /* END OF SPACE MAP MANAGEMENT ROUTINES                                   */
  170. /*                                                                        */
  171.  
  172.  
  173.  
  174. /*                                                                        */
  175. /* These routines handle making maps of used and free space on a given hd */
  176. /*                                                                        */
  177.  
  178. /*                                                                        */
  179. /* Routine  to build a 'used' space map for the given hard drive          */
  180. /*                                                                        */
  181. int fdiskUsedMapGen( HardDrive *hd, SpaceMap **map ) {
  182.     unsigned int i, first, last;
  183.     int          status;
  184.     unsigned int diskempty=0;
  185.     Partition    *p, *ep;
  186.     SpaceMapEntry m;
  187.     
  188.     /* find range of partitions to include                  */
  189.     /* if no partitions then its easy to compute free space */
  190.     if ((status=fdiskFirstPartition( hd, &first )) )
  191.     if (status != FDISK_ERR_BADNUM)
  192.         return status;
  193.     else
  194.         diskempty = 1;
  195.  
  196.     if (diskempty) {
  197.     first = 0;
  198.     last  = 0;
  199.     } else {
  200.     if ((status=fdiskLastPartition( hd, &last   )))
  201.         return status;
  202.     }
  203.     
  204.     fdiskSpaceMapInit( map );
  205.  
  206.     /* insert the Master Boot record */
  207.     m.start = 0;
  208.     m.size  = hd->geom.sectors;
  209.     fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  210.  
  211.     /* if no partitions we're free to go */
  212.     if (diskempty)
  213.     return FDISK_SUCCESS;
  214.  
  215.     /* otherwise go thru list and figure allocated space */
  216.     for (i=first; i <= last; i++) {
  217.     status = fdiskGetAttrPartition( hd, i, &p );
  218.     if (!status) {
  219.         if ((i<hd->limits.maxPrimary + 1)) {
  220.         /* this is a primary partition */
  221.         /* is it an extended partition? */
  222.         if (!fdiskIsExtended( p->type.current )) {
  223.             m.start = p->start.current;
  224.             m.size  = p->size.current;
  225.         } else {
  226.             /* this is the PEP */
  227.             /* we insert a used region for the PEPT */
  228.             m.start = p->start.current;
  229.             m.size  = hd->geom.sectors;
  230.         }
  231.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  232.         } else {
  233.         /* this is a  logical/extended partition pair.     */
  234.         /* We take into account the space used by the EPT  */
  235.         /* and the logical partition                       */
  236.  
  237.         /* first the EPT */
  238.         fdiskGetAttrExtended( hd, i, &ep );
  239.         m.start = ep->start.current;
  240.         m.size  = hd->geom.sectors;  /* EPT takes 1 sector but */
  241.                                              /* usually takes 1 head   */
  242.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  243.  
  244.         /* now the logical partition */
  245.         /* see if the offset is due to a true offset, or because */
  246.         /* of cyl/head/sector stuff  */
  247.         /* could probably use p->offset.current but not sure */
  248.         /* that is setup correctly (yet) */
  249.         if ((p->start.current-ep->start.current)<=hd->geom.sectors) {
  250.             m.start = ep->start.current;
  251.             m.size  = p->size.current +
  252.             (p->start.current-ep->start.current);
  253.         } else {
  254.             m.start = p->start.current;
  255.             m.size  = p->size.current;
  256.         }
  257.         fdiskSpaceMapAdd( *map, &m, hd->geom.sectors );
  258.         free(ep);
  259.         }
  260.         free(p);
  261.     }
  262.     }
  263.         
  264.     return FDISK_SUCCESS;
  265. }
  266.  
  267. /*                                                                        */
  268. /* Routine  to build a 'free' space map for the given hard drive          */
  269. /*                                                                        */
  270. int fdiskFreeMapGen( HardDrive *hd, SpaceMap **map ) {
  271.     unsigned int    i, first, diff;
  272.     int             status;
  273.     SpaceMapEntry   m;
  274.     SpaceMap        *umap;
  275.  
  276.     /* make a 'used' map, and invert it */
  277.     if ((status=fdiskUsedMapGen( hd, &umap )))
  278.     return status;
  279.     
  280.     fdiskSpaceMapInit( map );
  281.     
  282.     /* start with first sector, find first used sector */
  283.     /* and keep building free space map that way.      */
  284.     first = 0;
  285.     for (i=0; i < umap->num; i++) {
  286.     diff = umap->entry[i].start - first;
  287.     if (diff) {
  288.         m.start = first;
  289.         m.size  = diff;
  290.         fdiskSpaceMapAdd( *map, &m, 0 ); /* no fuzz needed */
  291.     }
  292.  
  293.     /* move over used block to next possible free space */
  294.     first = umap->entry[i].start + umap->entry[i].size;
  295.     }
  296.  
  297.     /* now handle the end */
  298.     diff = hd->totalsectors - first;
  299.     if (diff) {
  300.     m.start = first;
  301.     m.size  = diff;
  302.     fdiskSpaceMapAdd( *map, &m, 0 ); /* no fuzz needed */
  303.     }
  304.  
  305.     return FDISK_SUCCESS;
  306. }
  307.  
  308.  
  309. /* given a partition describing a request and a candidate freespace entry  */
  310. /* determine if the space will work                                        */
  311. /* Handles aligning to cylinder boundaries                                 */
  312. /* modifies partition p if the constraints worked out ok                   */
  313. /* Returns FDISK_ERR_NOFREE if nothing found                               */
  314. int fdiskCheckConstraints( HardDrive *hd, SpaceMapEntry *freespace,
  315.                Partition *p, unsigned int type ) {
  316.  
  317.     unsigned int lsize,  msize,  csize, size;
  318.     unsigned int lstart, mstart, cstart, start;
  319.     unsigned int lcyl,   mcyl,   ccyl, cyl;
  320.     unsigned int end;
  321.     unsigned int extstart, extsize, extend;
  322.     unsigned int tmp1, tmp2;
  323.     unsigned int fuzz;
  324.     unsigned int inpep;
  325.     unsigned int satisfied, satis1, satis2, pass;
  326.  
  327.     /* see if we're looking for a logical partition or not */
  328.     fuzz  = 0;
  329.     inpep = 0;
  330.     if (type & LOGICAL)
  331.     if (!hd->pep)
  332.         return FDISK_ERR_NOPEP;
  333.     else {
  334.         fuzz  = hd->geom.sectors;
  335.         inpep = 1;
  336.         fdiskQueryPEP( hd, &extstart, &extsize );
  337.         extend = extstart + extsize - 1;
  338.     }
  339.     else if (type & PRIMARY_EXTENDED)
  340.     fuzz = 32;
  341.     
  342.     /* setup all of the constrains                                     */
  343.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  344.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  345.     fdiskQueryConstraint(&p->endcyl, &ccyl, &lcyl,   &mcyl,
  346.                FDISK_ENDCYL_MIN,  FDISK_ENDCYL_MAX );
  347.     fdiskQueryConstraint(&p->start,  &cstart, &lstart,  &mstart,
  348.                FDISK_START_MIN,  FDISK_START_MAX );
  349.     
  350.     /* we have several constraints to satisfy, here we are interested  */
  351.     /* in the size and start requirements of the partition             */
  352.     /* First see if we have a big enough chunk of free space           */
  353.     size  = freespace->size;
  354.     start = freespace->start;
  355.     end   = start + size - 1;
  356.     
  357.     /* handle cylinder boundaries here */
  358.     fdiskRoundStartToCylinder(hd, &start);
  359.     fdiskRoundEndToCylinder(hd, &end);
  360.     size = end - start + 1;
  361.     
  362.     pass = 0;
  363.     satis1 = satis2 = 0;
  364.     while (pass < 2) {
  365.     /* make sure its big enough and is inside PEP if so desired */
  366.     satisfied = 0;
  367.     if (size  >= lsize && (!inpep || (start>=extstart && start<=extend))) {
  368.         end = start + lsize - 1;
  369.  
  370.         /* round end to the cylinder boundary */
  371.         fdiskRoundEndToCylinder( hd, &end );
  372.         
  373.         /* now check that we can satisfy and start/end contraints */
  374.         satisfied = 1;
  375.         if (fdiskConstraintIsActive( &p->endcyl )) {
  376.         fdiskSectorToCHS(hd,end,&cyl,&tmp1,&tmp2);
  377.         satisfied = satisfied && (cyl >= lcyl) && (cyl <= mcyl );
  378.         if (!pass && !satisfied && LastAllocStat == ALLOC_UNDEF)
  379.             LastAllocStat = ALLOC_CYL;
  380.         }
  381.         
  382.         if (fdiskConstraintIsActive( &p->start )) {
  383.         satisfied = satisfied && (start>=lstart) && (start<=mstart);
  384.         if (!pass && !satisfied && LastAllocStat == ALLOC_UNDEF)
  385.             LastAllocStat = ALLOC_START;
  386.         }
  387.         
  388.         if (inpep) {
  389.         satisfied = satisfied && (end <= extend);
  390.         }
  391.  
  392.         /* cant let swap get too big! */
  393.         if (p->type.current == LINUX_SWAP_PARTITION) {
  394.         unsigned int maxswap;
  395. #if defined(__alpha__)
  396.         maxswap = (8192-10)*8*8192;
  397. #else
  398.         maxswap = (4096-10)*8*4096;
  399. #endif
  400.         maxswap = maxswap / SECTORSIZE;
  401.         satisfied = satisfied && ((end-start+1) <= maxswap);
  402.         }
  403.     } else {
  404.         if (!pass && LastAllocStat == ALLOC_UNDEF)
  405.         LastAllocStat = ALLOC_SIZE;
  406.     }
  407.  
  408.     /* did we pass all the tests? */
  409.     if (pass == 0) {
  410.         satis1 = satisfied;
  411.         if (satisfied) {
  412.         /* save working params into partition entry */
  413.         p->size.current  = end - start + 1;
  414.         p->start.current = start;
  415.  
  416.         LastAllocStat = ALLOC_OK;
  417.         
  418.         /* now lets get greedy and grab extra cylinder    */
  419.         /* this makes up for the fact that we almost      */
  420.         /* always grab a little less space than requested */
  421.         /* due to overhead of partition tables            */
  422.         pass++;
  423.         lsize += hd->geom.heads*hd->geom.sectors;
  424.         if (lsize > size)
  425.             lsize = size;
  426.         } else {
  427.         pass = 3;
  428.         }
  429.     } else {
  430.         satis2 = satisfied;
  431.         if (satisfied) {
  432.         /* save working params into partition entry */
  433.         p->size.current  = end - start + 1;
  434.         p->start.current = start;
  435.  
  436.         /* we're done */
  437.         pass = 3;
  438.         } else {
  439.         /* we're done */
  440.         pass = 3;
  441.         }
  442.     }
  443.     }
  444.     
  445.     if (satis1 || satis2)
  446.     return FDISK_SUCCESS;
  447.     else
  448.     return FDISK_ERR_NOFREE;
  449. }
  450.  
  451. /* Looking at current partition table of drive hd, find a chunk of         */
  452. /* free space that will contain the partition p with all its constraints   */
  453. /* if inpep!=0, we look in pep area only, and add some space required      */
  454. /* for logical partitions over their requested size.                       */
  455. /* Handles aligning to cylinder boundaries                                 */
  456. /* Returns FDISK_ERR_NOFREE if nothing found                               */
  457. int fdiskFindFreeSlot( HardDrive *hd, SpaceMap *freespace, Partition *p,
  458.                unsigned int type, unsigned int *freeslot ) {
  459.  
  460.     unsigned int done, j;
  461.     
  462.     /* we have several constraints to satisfy, here we are interested  */
  463.     /* in the size and start requirements of the partition             */
  464.     /* First see if we have a big enough chunk of free space           */
  465.     done = 0;
  466.     for (j=0; j<freespace->num && !done; j++) {
  467.     if (fdiskCheckConstraints(hd, &freespace->entry[j],
  468.                   p, type ) == FDISK_SUCCESS) {
  469.         done = 1;
  470.         *freeslot = j;
  471.     }
  472.     }
  473.     
  474.     if (done) {
  475.     return FDISK_SUCCESS;
  476.     } else {
  477.     /* guess error if we didn't set it above */
  478.     if (LastAllocStat == ALLOC_UNDEF)
  479.         LastAllocStat = ALLOC_SIZE;
  480.     return FDISK_ERR_NOFREE;
  481.     }
  482. }
  483.  
  484. /* characteristics of primary are handled in constraints in p        */
  485. /* if pri < 0, autoallocate primary slot                             */
  486. int fdiskMakeNewPrimary( HardDrive *hd, int pri, Partition *p ) {
  487.     
  488.     unsigned int lsize,  msize,  csize;
  489.     unsigned int lstart, mstart, cstart;
  490.     unsigned int lcyl,   mcyl,   ccyl;
  491.     int          status;
  492.     
  493.     Partition *pt;
  494.  
  495.     /* See if we need to auto-allocate the partition */
  496.     if (pri < 0)
  497.     if (fdiskFindFreePrimary( hd, &pri ) == FDISK_ERR_NOFREEPRIM) {
  498.         LastAllocStat = ALLOC_FREEPRI;
  499.         return FDISK_ERR_NOFREEPRIM;
  500.     }
  501.     
  502.     /* setup all of the constrains                                     */
  503.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  504.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  505.     fdiskQueryConstraint(&p->endcyl, &ccyl, &lcyl,   &mcyl,
  506.                FDISK_ENDCYL_MIN,  FDISK_ENDCYL_MAX );
  507.     fdiskQueryConstraint(&p->start,  &cstart, &lstart,  &mstart,
  508.                FDISK_START_MIN,  FDISK_START_MAX );
  509.     
  510.     status=fdiskCreatePrimary( hd, pri );
  511.     if (status != FDISK_SUCCESS) {
  512.     LastAllocStat = ALLOC_FREEPRI;
  513.     return status;
  514.     }
  515.     
  516.     fdiskGetAttrPartition( hd, 1, &pt );
  517.     fdiskSetConstraint( &pt->size,  csize,  lsize,  msize,
  518.             fdiskConstraintIsActive(&p->size) );
  519.     fdiskSetConstraint( &pt->start, cstart, lstart, mstart,
  520.             fdiskConstraintIsActive(&p->start) );
  521.     fdiskSetFixedConstraint( &pt->type,   p->type.current    );
  522.     fdiskSetFixedConstraint( &pt->active, p->active.current  );
  523.     fdiskSetFixedConstraint( &pt->offset, 0                  );
  524.     fdiskDeactivateAllDriveSet( &pt->drive );
  525.     fdiskActivateDriveSet( &pt->drive,  hd->num );
  526.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  527.     fdiskSetFixedConstraint( &pt->num,    pri                );
  528.     pt->status = ALLOCATED;
  529.  
  530.     fdiskSetAttrPartition( hd, pri, pt );
  531.  
  532.     /* store current value in the partition we were passed */
  533.     fdiskSetCurrentConstraint(&p->num, pri);
  534.     fdiskSetCurrentDriveSet(&p->drive, hd->num);
  535.     fdiskSetCurrentConstraint(&p->size, csize);
  536.     fdiskSetCurrentConstraint(&p->start, cstart);
  537.     
  538.     free(pt);
  539.  
  540.     return FDISK_SUCCESS;
  541. }    
  542.  
  543. /* if no primary extended partition exists, this routine will do it */
  544. int fdiskMakeNewPrimaryExtended(HardDrive *hd,
  545.                 int          pep,
  546.                 unsigned int freestart,
  547.                 unsigned int freesize ) {
  548.  
  549.     unsigned int extstart, extend, extsize;
  550.     int          status;
  551.  
  552.     Partition *pt;
  553.     
  554.     /* no primary extended partition (yet)                            */
  555.     /* lets make one the size of the free space block we're putting   */
  556.     /* the requested partition in                                     */
  557.     /* then we make our logical partition                             */
  558.     if (pep < 0)
  559.     if (fdiskFindFreePrimary( hd, &pep ) == FDISK_ERR_NOFREEPRIM) {
  560.         LastAllocStat = ALLOC_FREEPRI;
  561.         return FDISK_ERR_NOFREEPRIM;
  562.     }
  563.     
  564.     hd->pep = pep;
  565.     if ((status=fdiskCreatePrimary( hd, pep )) != FDISK_SUCCESS) {
  566.     LastAllocStat = ALLOC_FREEPRI;
  567.     return status;
  568.     }
  569.     
  570.     fdiskGetAttrPartition( hd, pep, &pt );
  571.     
  572.     /* we need to make size/start that of the free block we're using */
  573.     /* and NOT the size of the logical partition we want to make     */
  574.     /* We DO NOT set the size/start constraints ACTIVE, since we may */
  575.     /* want to grow them later.                                      */
  576.     extstart = freestart;
  577.     extend   = freestart + freesize - 1;
  578.     
  579.     /* handle cylinder boundaries here */
  580.     fdiskRoundStartToCylinder(hd, &extstart);
  581.     fdiskRoundEndToCylinder(hd, &extend);
  582.     extsize = extend - extstart + 1;
  583.     
  584.     fdiskSetConstraint( &pt->size, extsize,  extsize,  FDISK_SIZE_MAX, 0 );
  585.     fdiskSetConstraint( &pt->start,extstart, extstart, FDISK_START_MAX, 0);
  586.     fdiskSetFixedConstraint( &pt->type,   DOS_EXTENDED_PARTITION );
  587.     fdiskSetFixedConstraint( &pt->active, 0 );
  588.     fdiskSetFixedConstraint( &pt->offset, 0 );
  589.     fdiskDeactivateAllDriveSet( &pt->drive );
  590.     fdiskActivateDriveSet( &pt->drive,  hd->num  );
  591.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  592.     fdiskSetFixedConstraint( &pt->num,    pep );
  593.     pt->status = ALLOCATED;
  594.     
  595.     fdiskSetAttrPartition( hd, pep, pt );
  596.     free(pt);
  597.  
  598.     return FDISK_SUCCESS;
  599. }
  600.  
  601. /* Make an extended partition within the specified region */
  602. /* Must have a PEP before this call will work.            */
  603. /* The size and start of the partition p are used         */
  604. /* However, the user data is offset because there is a EPT*/
  605. /* at the start of this space                             */
  606. int fdiskMakeNewLogical( HardDrive *hd, Partition *p ) {
  607.     int status;
  608.  
  609.     unsigned int lp, pep;
  610.  
  611.     unsigned int cstart, lstart, mstart;
  612.     unsigned int csize,  lsize,  msize;
  613.     unsigned int extstart, extend, extsize;
  614.     unsigned int sector_offset;
  615.     
  616.     Partition *pt, *ept;
  617.  
  618.     /* see if pep exists */
  619.     pep = hd->pep;
  620.     if (!pep)
  621.     return FDISK_ERR_NOPEP;
  622.     
  623.     /* use it as a template for the extented partition part of the */
  624.     /* EP/LP pair we are creating                                  */
  625.     if ((status=fdiskAppendLogical( hd, &lp )) != FDISK_SUCCESS)
  626.     return status;
  627.  
  628.  
  629.     /* setup all of the constrains                              */
  630.     fdiskQueryConstraint(&p->size,  &csize, &lsize,  &msize,
  631.                FDISK_SIZE_MIN, FDISK_SIZE_MAX );
  632.     fdiskQueryConstraint(&p->start, &cstart, &lstart,  &mstart,
  633.                FDISK_START_MIN,  FDISK_START_MAX );
  634.     
  635.     /* get initial starting points for extended and logical entries */
  636.     fdiskGetAttrPartition( hd, lp,  &pt );
  637.     fdiskGetAttrPartition( hd, pep, &ept );
  638.     
  639.     /* since we are creating a logical partition from scratch,  */
  640.     /* we can make the offset anything we like. The existing    */
  641.     /* 'fdisk' program makes the offset equal to one head       */
  642.     sector_offset = hd->geom.sectors;
  643.  
  644.     /* setup the extended partition first */
  645.     /* it describes the partition which the logical is IN       */
  646.     extstart = cstart;
  647.     extend   = cstart + csize + sector_offset - 1;
  648.     
  649.     /* handle cylinder boundaries here */
  650.     fdiskRoundStartToCylinder(hd, &extstart);
  651.     fdiskRoundEndToCylinder(hd, &extend);
  652.     extsize = extend - extstart + 1;
  653.     
  654.     fdiskSetConstraint( &ept->size, extsize,  extsize,  FDISK_SIZE_MAX, 0 );
  655.     fdiskSetConstraint( &ept->start,extstart, extstart, FDISK_START_MAX, 0);
  656.     fdiskSetFixedConstraint( &ept->type,   DOS_EXTENDED_PARTITION );
  657.     fdiskSetFixedConstraint( &ept->active, 0 );
  658.     fdiskSetFixedConstraint( &ept->offset, 0 );
  659.     fdiskDeactivateAllDriveSet( &ept->drive );
  660.     fdiskActivateDriveSet( &ept->drive,  hd->num  );
  661.     fdiskSetCurrentDriveSet( &ept->drive, hd->num );
  662.     fdiskSetFixedConstraint( &ept->num,  lp );
  663.     ept->status = ALLOCATED;
  664.     
  665.     fdiskSetAttrExtended( hd, lp, ept );
  666.     free(ept);
  667.     
  668.     /* now the logical partition                                */
  669.     fdiskSetConstraint( &pt->size,
  670.             extsize-sector_offset,
  671.             lsize, msize, fdiskConstraintIsActive(&p->size) );
  672.     fdiskSetConstraint( &pt->start,
  673.             extstart+sector_offset,
  674.             lstart, mstart,fdiskConstraintIsActive(&p->start) );
  675.     fdiskSetFixedConstraint( &pt->type,   p->type.current );
  676.     fdiskSetFixedConstraint( &pt->active, p->active.current );
  677.     fdiskSetFixedConstraint( &pt->offset, 0 );
  678.     fdiskDeactivateAllDriveSet( &pt->drive );
  679.     fdiskActivateDriveSet( &pt->drive,  hd->num  );
  680.     fdiskSetCurrentDriveSet( &pt->drive, hd->num );
  681.     fdiskSetFixedConstraint( &pt->num,    lp );
  682.     pt->status = ALLOCATED;
  683.     
  684.     /* store current value in the partition we were passed */
  685.     fdiskSetCurrentConstraint(&p->num, lp);
  686.     fdiskSetCurrentDriveSet(&p->drive, hd->num);
  687.     fdiskSetCurrentConstraint(&p->size, extsize-sector_offset);
  688.     fdiskSetCurrentConstraint(&p->start, extstart+sector_offset);
  689.     
  690.     fdiskSetAttrPartition( hd, lp, pt );
  691.     free(pt);
  692.  
  693.     return FDISK_SUCCESS;
  694. }
  695.  
  696.  
  697. /*                                                                        */
  698. /* These routines handle inserting a desired partition into an existing   */
  699. /* partition table on a hard drive.                                       */
  700. /*                                                                        */
  701. /* We pass an array of HardDrive's, each of which is considered for the   */
  702. /* possible home of the partition.                                        */
  703. /* HardDrive's are assumed to be in arranged in increasing number         */
  704. /* Note that the index of the drive in the HardDrive array IS NOT the same*/
  705. /* as its actual 'num'.                                                   */
  706. int fdiskAutoInsertPartition(HardDrive **hdarr,
  707.                  unsigned int nhd,
  708.                  Partition *p ) {
  709.     
  710.     unsigned int drive;
  711.     unsigned int extstart, extsize;
  712.     unsigned int i;
  713.     unsigned int freeslot, freedrive;
  714.  
  715.     unsigned int extExists, priExists, noneExists;
  716.     unsigned int extCreate, priCreate, logCreate;
  717.     unsigned int extTried,  priTried, logTried;
  718.     unsigned int done, donesearch, errsearch, lasttry, trynext;
  719.     int status;
  720.  
  721.     HardDrive *hd;
  722.     SpaceMap  **freespace;
  723.     DriveSet  drives;
  724.     Partition *ptmp;
  725.  
  726.     /* first lets generate free space maps for all possible drives */
  727.     /* also figure out what range of drives exist                  */
  728.     /* index of freespace[] will be the same as for accessing      */
  729.     /* the entries of the hdarr[] of HardDrive's                   */
  730.     freespace = (SpaceMap **) alloca((nhd)*sizeof(SpaceMap));
  731.     fdiskDeactivateAllDriveSet( &drives );
  732.     for (drive=0; drive < nhd; drive++) {
  733.     fdiskFreeMapGen( hdarr[drive], &freespace[drive] );
  734.     fdiskActivateDriveSet( &drives, hdarr[drive]->num );
  735.     }
  736.  
  737.     /* loop over all the drives which are valid to consider            */
  738.     /* For each drive, go through a list of 'preferable' places to put */
  739.     /* the new partition.                                              */
  740.     /*                                                                 */
  741.     /* Rules:                                                          */
  742.     /*                                                                 */
  743.     /*     If No Partitions Exist                                      */
  744.     /*        Create New Primary                                       */
  745.     /*        DONE                                                     */
  746.     /*     Else If No Extended Exists                                  */
  747.     /*        Create Extended in largest hole fitting all constraints  */
  748.     /*        DONE                                                     */
  749.     /*     Else                                                        */
  750.     /*        Try to create a logical partition                        */
  751.     /*        If Success                                               */
  752.     /*           DONE                                                  */
  753.     /*        Else                                                     */
  754.     /*           Try to create a primary partition                     */
  755.     /*           If Success                                            */
  756.     /*              DONE                                               */
  757.     /*           Else                                                  */
  758.     /*              FAIL                                               */
  759.     /*                                                                 */
  760.     done = 0;
  761.     for (drive = 0; drive < nhd && !done; drive++) {
  762.     LastAllocStat = ALLOC_UNDEF;
  763.     hd = hdarr[drive];
  764.     if (!fdiskThisDriveSetIsActive( &p->drive, hd->num ))
  765.         continue;
  766.     
  767.     /* Figure out what partitions currently exist on this drive */
  768.     extExists  = (hd->pep != 0);
  769.     priExists = 0;
  770.     for (i=1; i< hd->limits.maxPrimary; i++) {
  771.         if (fdiskGetAttrPrimary(hd, i, &ptmp) != FDISK_SUCCESS)
  772.         continue;
  773.         priExists |= !fdiskIsExtended(ptmp->type.current);
  774.     }
  775. /*    priExists  = !(fdiskLastPartition( hd, &tmp1 ) == FDISK_ERR_BADNUM); */
  776.     noneExists = !(extExists || priExists);
  777.  
  778.     /* Keeps trying strategies for placing new partition in existing */
  779.     /* scheme until we hit a solution we like                        */
  780.     donesearch = 0;
  781.     errsearch  = 0;
  782.     lasttry    = 0;
  783.     trynext    = 0;
  784.     extTried   = (hd->limits.maxPrimary == hd->limits.maxPartitions);
  785.     logTried   = 0;
  786.     priTried   = 0;
  787.     while (!donesearch && !errsearch && !lasttry && !trynext) {
  788.         priCreate  = 0;
  789.         extCreate  = 0;
  790.         logCreate  = 0;
  791.         
  792.         if (noneExists || !priExists) {
  793.         /* gonna make a primary partition */
  794.         priCreate = 1;
  795.         if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  796.                       PRIMARY,&freeslot)) != FDISK_SUCCESS)
  797.             trynext = 1;
  798.         else {
  799.             freedrive  = drive;
  800.             lasttry = 1;
  801.         }
  802.         } else if (!extExists) {
  803.  
  804.         if (!extTried) {
  805.             /* let try to make a primary extended partition */
  806.             extCreate = 1;
  807.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  808.                           PRIMARY_EXTENDED,
  809.                           &freeslot)) != FDISK_SUCCESS)
  810.             trynext = 1;
  811.             else {
  812.             freedrive  = drive;
  813.             }
  814.         } else if (!priTried) {
  815.             /* couldnt make extended work, try to make another PP */
  816.             priCreate = 1;
  817.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  818.                       PRIMARY,&freeslot)) != FDISK_SUCCESS)
  819.             trynext = 1;
  820.             else {
  821.             freedrive  = drive;
  822.             lasttry    = 1;
  823.             }
  824.         } else
  825.             /* nothing else to try */
  826.             trynext = 1;
  827.         } else {
  828.         /* try to make a logical first, then a primary */
  829.         if (!logTried) {
  830.             logCreate = 1; 
  831.             if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  832.                       LOGICAL,&freeslot)) != FDISK_SUCCESS) {
  833.             if (!priTried) {
  834.                 priCreate = 1;
  835.                 if ((status=fdiskFindFreeSlot(hd,freespace[drive],p,
  836.                               PRIMARY,&freeslot)) != FDISK_SUCCESS)
  837.                 trynext = 1;
  838.                 else {
  839.                 freedrive  = drive;
  840.                 lasttry    = 1;
  841.                 }
  842.             } else {
  843.             trynext = 1;
  844.             }
  845.             } else {
  846.             freedrive  = drive;
  847.             }
  848.         } else
  849.             /* nothing else to try */
  850.             trynext = 1;
  851.         }
  852.  
  853.         /* move on to next drive */
  854.         if (trynext)
  855.         continue;
  856.         
  857.         if (!errsearch) {
  858.         /* now try to create whatever we decided was the best choice */
  859.         /* parameters of the allocated partition are in the partition*/
  860.         /* structure 'p'                                             */
  861.         if (priCreate) {
  862.             priTried = 1;
  863.             if ((status=fdiskMakeNewPrimary(hd,-1,p))==FDISK_SUCCESS)
  864.             donesearch = 1;
  865.         } else if (extCreate) {
  866.             extTried = 1;
  867.             if (!extExists) {
  868.             /* gotta make a PEP */
  869.             extstart = freespace[drive]->entry[freeslot].start;
  870.             extsize  = freespace[drive]->entry[freeslot].size;
  871.             status=fdiskMakeNewPrimaryExtended(hd, -1,
  872.                                extstart,extsize);
  873.             if (status == FDISK_SUCCESS) {
  874.                 extExists = 1;
  875.                 status=fdiskMakeNewLogical(hd, p);
  876.                 if (status == FDISK_SUCCESS)
  877.                 donesearch = 1;
  878.             }
  879.             }
  880.         } else if (logCreate) {
  881.             logTried = 1;
  882.             if (!extExists) {
  883.             status = FDISK_ERR_NOPEP;
  884.             errsearch = 1;
  885.             } else {
  886.             status=fdiskMakeNewLogical(hd, p);
  887.             if (status == FDISK_SUCCESS)
  888.                 donesearch = 1;
  889.             }
  890.         }            
  891.         } else {
  892.         printf("Error searching was %d, aborting\n", status);
  893.         return status;
  894.         }
  895.     }
  896.  
  897.     if (donesearch)
  898.         done = 1;
  899.     }
  900.         
  901.     /* did we find an acceptable location?                  */
  902.     /* if not we SHOULD try reshuffling existing partitions */
  903.     /* but for now we just give up                          */
  904.     if (!done) {
  905.     return FDISK_ERR_NOFREE;
  906.     }
  907.  
  908.     return FDISK_SUCCESS;
  909. }
  910.  
  911.  
  912. /* not sure what this will be good for yet */
  913. #if 0
  914.  
  915. /* moves a non-extended primary partition to new location specified in */
  916. /* the partition p                                                     */
  917. int fdiskMovePrimary( HardDrive *hd, unsigned int num, Partition *p ) {
  918.  
  919.     fdiskSetAttrPartition( hd, num, &p);
  920.  
  921. }
  922.  
  923. /* krunch partition table so all moveable partitions form contiguous block */
  924. /* will not slide logical partitions out of an extended partition, instead */
  925. /* the extended partition start is slid and logical partitions move inside */
  926. /* the extended partition. This way the # of primary partition slots used  */
  927. /* is kept constant.                                                       */
  928. /* we try to push available free space towards the start of the disk       */
  929. int fdiskKrunchPartitionTable( HardDrive *hd ) {
  930.  
  931.     unsigned int last, first, cur;
  932.     unsigned int csize,  lsize,  msize, asize;
  933.     unsigned int cstart, lstart, mstart, astart;
  934.     unsigned int endfree, startfree, sizefree;
  935.     unsigned lastfree;
  936.     int      i;
  937.     SpaceMap *freespace;
  938.     SpaceMapEntry testentry;
  939.     Partition tstp;
  940.     Partition *p, *ep;
  941.  
  942.     /* make sure there are any partitions to process */
  943.     if (fdiskLastPartition(hd, &last ) == FDISK_ERR_BADNUM)
  944.     return FDISK_ERR_BADNUM;
  945.     
  946.     /*  - look through freespace list                                    */
  947.     /*  - if adjacent, movable partition exists, slide to close space    */
  948.     /*    otherwise, find movable partitions to move to close   space    */
  949.     /*  - if we made any changes, recompute freespace map                */
  950.     /*  - keep going till we change nothing                              */
  951.     /*                                                                   */
  952.     /* First look at primary partitions, shift/relocate them if possible */
  953.     done      = 0;
  954.     lastfree  = hd->totalsectors;
  955.     freespace = NULL;
  956.     while (!done) {
  957.  
  958.     /* get a freespace map for the drive first */
  959.     fdiskFreeMapGen( hd, &freespace );
  960.     if (!freespace->num)
  961.         break;
  962.  
  963.     /* locate next free space to consider */
  964.     for (i=0; i < freespace->num; i++)
  965.         if (freespace->entry[i].start < lastfree)
  966.         break;
  967.  
  968.     /* couldnt find any more freespace to consider */
  969.     if (i == freespace->num)
  970.         break;
  971.     
  972.     /* locate primary partition closest to freespace on the high side */
  973.     startfree = freespace->entry[i].start;
  974.     sizefree = freespace->entry[i].size;
  975.     endfree   = startfree + sizefree - 1;
  976.  
  977.     mindiff = FDISK_SIZE_MAX;
  978.     minnum  = 0;
  979.     for (cur=1; cur <=hd->limits.maxPrimary; cur++) {
  980.         if (fdiskGetAttrPartition( hd, cur, &p))
  981.         continue;
  982.  
  983.         if (p->immutable) {
  984.         free(p);
  985.         continue;
  986.         }
  987.         
  988.         fdiskGetConstraint(&p->start,&cstart,&lstart,&mstart,&astart );
  989.         fdiskGetConstraint(&p->size, &csize, &lsize, &msize, &asize  );
  990.  
  991.         if (cstart < startfree) {
  992.         tmpdiff = startfree - cstart;
  993.         if (tmpdiff < mindiff) {
  994.             mindiff = tmpdiff;
  995.             minnum  = cur;
  996.         }
  997.         }
  998.         free(p);
  999.     }
  1000.  
  1001.     /* see if we found anything */
  1002.     if ( minnum != 0 ) {
  1003.         fdiskGetAttrPartition( hd, minnum, &p);
  1004.  
  1005.         if (!fdiskIsExtended(p->type.current)) {
  1006.         /* its a simple primary partition               */
  1007.         /* see if we can move the partition and satisfy */
  1008.         /* any constraints if may have on its location  */
  1009.         /* if it works, move the partition and update   */
  1010.         /* last free considered                         */
  1011.         fdiskGetConstraint(&p->start,&cstart,
  1012.                    &lstart,&mstart,&astart );
  1013.         fdiskGetConstraint(&p->size, &csize,
  1014.                    &lsize, &msize, &asize  );
  1015.         startfree = freespace->entry[minnum].start;
  1016.         sizefree  = freespace->entry[minnum].size;
  1017.         endfree   = startfree + sizefree - 1;
  1018.  
  1019.         /* setup new location and round to a cyl boundary */
  1020.         /* if rounding makes the partition smaller, move  */
  1021.         /* start back another cylinder and try again      */
  1022.         /* primary partitions always start on a cylinder  */
  1023.         /* boundary (except for the one containing the MBR*/
  1024.         testentry.start = endfree - csize;
  1025.         fdiskRoundStartToCylinder( hd, &cstart );
  1026.         testentry.size  = endfree - cstart + 1;
  1027.         if (testentry.size < csize)
  1028.             testentry.start -= hd->geom.sectors*hd->geom.heads;
  1029.         testentry.size  = csize;
  1030.         
  1031.         if (fdiskCheckContraints(hd, &testentry,
  1032.                      p, PRIMARY ) == FDISK_SUCCESS) {
  1033.             fdiskMovePrimary(hd, minnum, p);
  1034.             fdiskGetConstraint(&p->start,&cstart,
  1035.                        &lstart,&mstart,&astart );
  1036.             fdiskGetConstraint(&p->size, &csize,
  1037.                        &lsize, &msize, &asize  );
  1038.             lastfree = cstart + csize;
  1039.         }
  1040.         } else {
  1041.         /* its a primary extended partition, lots more to do!  */
  1042.         /* have to also relocate all logical partitions inside */
  1043.         if (fdiskCheckContraints(hd, &freespace->entry[i],
  1044.                      p, EXTENDED ) == FDISK_SUCCESS) {
  1045.             fdiskMovePrimaryExtended( hd, minnum, p );
  1046.             fdiskGetConstraint(&p->start,&cstart,
  1047.                        &lstart,&mstart,&astart );
  1048.             fdiskGetConstraint(&p->size, &csize,
  1049.                        &lsize, &msize, &asize  );
  1050.             lastfree = cstart + csize;
  1051.         }
  1052.  
  1053.         }
  1054.     } else {
  1055.         done = 1;
  1056.     }
  1057.     
  1058.     /* anything left allocated? */
  1059.     if (freespace != NULL) {
  1060.         fdiskSpaceMapFree( freespace );
  1061.         freespace = NULL;
  1062.     }
  1063.     }
  1064.  
  1065.     /* anything left allocated? */
  1066.     if (freespace != NULL) {
  1067.     fdiskSpaceMapFree( freespace );
  1068.     freespace = NULL;
  1069.     }
  1070.     
  1071. }
  1072. #endif
  1073.  
  1074.  
  1075. /* given a list of requested partitions, take hdarr as starting point.  */
  1076. /* stick partitions into nhdarr                                         */
  1077. static int dofdiskAutoInsertPartitions( HardDrive **hdarr,    
  1078.                    unsigned int numhd,
  1079.                    HardDrive **newhdarr, 
  1080.                    PartitionSpec *spec, int wecare ) {
  1081.     unsigned int i;
  1082.     int          status;
  1083.     /* copy existing hard drive structure into the new hard drive struct */
  1084.     for (i=0; i < numhd; i++) 
  1085.     memcpy(newhdarr[i], hdarr[i], sizeof(HardDrive));
  1086.  
  1087.     /* start inserting the partitions */
  1088.     /* set the last alloc error to undef */
  1089.     LastAllocStat = ALLOC_UNDEF;
  1090.     for (i=0; i<spec->num; i++) {
  1091.     if (spec->entry[i].status != REQUEST_ORIGINAL) {
  1092.         status = fdiskAutoInsertPartition( newhdarr, numhd,
  1093.                            &spec->entry[i].partition );
  1094.         if (status == FDISK_SUCCESS) {
  1095.         spec->entry[i].status = REQUEST_GRANTED;
  1096.         if (wecare) spec->entry[i].reason = ALLOC_OK;
  1097.         } else {
  1098.         spec->entry[i].status = REQUEST_DENIED;
  1099.         if (wecare) spec->entry[i].reason = LastAllocStat;
  1100.         }
  1101.     }
  1102.     }
  1103.     
  1104.     return FDISK_SUCCESS;
  1105. }
  1106.  
  1107. int fdiskAutoInsertPartitions(HardDrive **hdarr,    unsigned int numhd,
  1108.                   HardDrive **newhdarr, 
  1109.                   PartitionSpec *spec) {
  1110.     return dofdiskAutoInsertPartitions(hdarr, numhd, newhdarr, spec, 1);
  1111. }
  1112.  
  1113.  
  1114. /*                                                                   */
  1115. /* growing routines                                                  */
  1116. /* these routines take an existing array for drives and a partspec   */
  1117. /* and grow the partitions marked for growth to fill available space */
  1118.  
  1119. /* this should work but is VERY messy!!!!! */
  1120. /* uses internals of partitions and partitions specs too much */
  1121. /* needs to be rewritten to use functions to get/set values   */
  1122. int fdiskGrowPartitions( HardDrive **hdarr, unsigned int numhd,
  1123.              HardDrive **newhdarr, 
  1124.              PartitionSpec *spec ) {
  1125.  
  1126.     PartitionSpec trialspec, startspec, origspec;
  1127.     Partition     *p;
  1128.     unsigned int  *freespace, *usedbygrow;
  1129.     unsigned int  min, max, cur, dif, ldif;
  1130.     int           j, k, l;
  1131.     int           statcur;
  1132.     float         f;
  1133.     
  1134.     /* copy existing partition spec in a safe place  */
  1135.     /* we make new copies of the 'names' field, since its malloc'd */
  1136.     memcpy(&startspec, spec, sizeof(PartitionSpec));
  1137.     for (j=0; j<spec->num; j++) {
  1138.     /* copy the name */
  1139.     if (spec->entry[j].name)
  1140.         startspec.entry[j].name = strdup(spec->entry[j].name);
  1141.  
  1142.     /* if request was granted, lock partition to drive its on currently */
  1143.     if (spec->entry[j].status == REQUEST_GRANTED) {
  1144.         startspec.entry[j].status = REQUEST_PENDING;
  1145.         p = &startspec.entry[j].partition;
  1146.         fdiskDeactivateAllDriveSet( &p->drive );
  1147.         fdiskActivateDriveSet( &p->drive, p->drive.current );
  1148.     }    
  1149.     }
  1150.  
  1151.     /* go thru and weed out the denied partitions */
  1152.     for (j=0; j<spec->num; j++)
  1153.     if (spec->entry[j].status == REQUEST_DENIED)
  1154.         fdiskDeletePartitionSpec(&startspec, spec->entry[j].name);
  1155.         
  1156.     /* make array of freespace left on each drive */
  1157.     freespace  = (unsigned int *) alloca(numhd*sizeof(unsigned int));
  1158.     usedbygrow = (unsigned int *) alloca(numhd*sizeof(unsigned int));
  1159.     for (j=0; j<numhd; j++) {
  1160.     freespace[j] = hdarr[j]->totalsectors;
  1161.     usedbygrow[j] = 0;
  1162.     }
  1163.     
  1164.     for (j=0; j<startspec.num; j++) {
  1165.     p = &startspec.entry[j].partition;
  1166.     if (fdiskIsExtended(p->type.current))
  1167.         continue;
  1168.         
  1169.     for (k=0; k<numhd; k++)
  1170.         if (hdarr[k]->num == p->drive.current)
  1171.         break;
  1172.  
  1173.     if (k==numhd) /* shouldnt happen */
  1174.         continue;
  1175.     
  1176.     freespace[k] -= p->size.current;
  1177.  
  1178.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1179.         continue;
  1180.     usedbygrow[k] += p->size.current;
  1181.     }
  1182.  
  1183.     /* now grow them */
  1184.     memcpy(&trialspec, &startspec, sizeof(PartitionSpec));
  1185.     for (j=0; j<startspec.num; j++) {
  1186.     p = &startspec.entry[j].partition;
  1187.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1188.         continue;
  1189.     
  1190.     for (k=0; k<numhd; k++)
  1191.         if (hdarr[k]->num == p->drive.current)
  1192.         break;
  1193.  
  1194.     if (k==numhd) /* shouldnt happen */
  1195.         continue;
  1196.  
  1197.     /* OK, this is the ugliest binary search ever coded. */
  1198.     min = 0;
  1199.     if (usedbygrow[k] != 0)
  1200.         f = ((float)p->size.current/(float)usedbygrow[k]);
  1201.     else
  1202.         f = 0; /* shouldnt happen */
  1203.     max = (unsigned int)((f*(float)freespace[k])+0.5);
  1204.     cur = max - (max-min)/2; /* might help with rounding */
  1205.     dif = max - min;
  1206.     ldif = 0;
  1207.  
  1208.     while (min != max && ldif != dif) {
  1209.         trialspec.entry[j].status   = REQUEST_PENDING;
  1210.         trialspec.entry[j].partition.size.min =
  1211.         startspec.entry[j].partition.size.min + cur;
  1212.         statcur = dofdiskAutoInsertPartitions(hdarr, numhd, newhdarr, 
  1213.                               &trialspec, 0);
  1214.  
  1215.         /* check to see if any partitions got lost, if so thats bad */
  1216.         for (l=0; l<trialspec.num; l++)
  1217.         if (trialspec.entry[l].status == REQUEST_DENIED) {
  1218.             statcur = FDISK_ERR_NOFREE;
  1219.             break;
  1220.         }
  1221.     
  1222.         if (statcur != FDISK_SUCCESS)
  1223.         max = cur;
  1224.         else
  1225.         min = cur;
  1226.  
  1227.         cur = max - (max-min)/2;
  1228.         ldif = dif;
  1229.         dif  = max - min;
  1230.     }
  1231.  
  1232.     /* store the final working size in trialspec */
  1233.     /* max COULD have failed, so we have to look */
  1234.     /* at result of last try with it to see if   */
  1235.     /* we should use it instead of min. Min val  */
  1236.     /* SHOULD always be a successful size.       */
  1237.     trialspec.entry[j].status   = REQUEST_PENDING;
  1238.     trialspec.entry[j].partition.size.min =
  1239.         startspec.entry[j].partition.size.min +
  1240.         ((statcur == FDISK_SUCCESS) ? cur : min);
  1241.     }
  1242.  
  1243.     /* we're done, copy into original partition spec and */
  1244.     /* insert one last time                              */
  1245.     memcpy(&origspec, spec, sizeof(PartitionSpec));
  1246.     for (j=0; j<startspec.num; j++) {
  1247.     p = &startspec.entry[j].partition;
  1248.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1249.         continue;
  1250.  
  1251.     for (k=0; k<spec->num; k++)
  1252.         if (!strcmp(trialspec.entry[j].name,spec->entry[k].name))
  1253.         break;
  1254.  
  1255.     if (k == spec->num) /* shouldnt happen */
  1256.         continue;
  1257.  
  1258.     spec->entry[k].partition.size.min=trialspec.entry[j].partition.size.min;
  1259.     spec->entry[k].status = REQUEST_PENDING;
  1260.     }
  1261.  
  1262.     dofdiskAutoInsertPartitions(hdarr, numhd, newhdarr, spec, 0);
  1263.  
  1264.     /* now put the 'min' size back to what the user wanted */
  1265.     for (j=0; j<spec->num; j++) {
  1266.     p = &spec->entry[j].partition;
  1267.     if (!p->size.active || p->size.min == p->size.max || p->immutable)
  1268.         continue;
  1269.  
  1270.     spec->entry[j].partition.size.min=origspec.entry[j].partition.size.min;
  1271.     }
  1272.     
  1273.     
  1274.     /* now clean up and leave */
  1275.     for (j=0; j<startspec.num; j++)
  1276.     free(startspec.entry[j].name);
  1277.     
  1278.     return FDISK_SUCCESS;
  1279. }
  1280.     
  1281.     
  1282.