home *** CD-ROM | disk | FTP | other *** search
/ Chip 1998 February / CHIP_2_98.iso / misc / src / rpm / lib / falloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-17  |  10.9 KB  |  436 lines
  1. #include "config.h"
  2.  
  3. #if HAVE_ALLOCA_H
  4. # include <alloca.h>
  5. #endif
  6.  
  7. #include <fcntl.h>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <unistd.h>
  11.  
  12. #include "falloc.h"
  13.  
  14. #define FA_MAGIC      0x02050920
  15.  
  16. /* 
  17.    The entire file space is thus divided into blocks with a "struct fablock"
  18.    at the header of each. The size fields doubly link this block list.
  19.  
  20.    There is an additional free list weaved through the block list, which 
  21.    keeps new allocations fast.
  22.  
  23.    Much of this was inspired by Knuth vol 1.
  24.  */
  25.  
  26. struct faFileHeader{
  27.     unsigned int magic;
  28.     unsigned int firstFree;
  29. };
  30.  
  31. struct faHeader {
  32.     unsigned int size;                
  33.     unsigned int freeNext; /* offset of the next free block, 0 if none */
  34.     unsigned int freePrev; 
  35.     unsigned int isFree;
  36.  
  37.     /* note that the u16's appear last for alignment/space reasons */
  38. };
  39.  
  40. struct faFooter {
  41.     unsigned int size;
  42.     unsigned int isFree; 
  43. } ;
  44.  
  45. /* flags here is the same as for open(2) - NULL returned on error */
  46. faFile faOpen(char * path, int flags, int perms) {
  47.     struct faFileHeader newHdr;
  48.     struct faFile_s fas;
  49.     faFile fa;
  50.     off_t end;
  51.  
  52.     if (flags & O_WRONLY) {
  53.     return NULL;
  54.     }
  55.     if (flags & O_RDWR) {
  56.     fas.readOnly = 0;
  57.     } else {
  58.     fas.readOnly = 1;
  59.     }
  60.  
  61.     fas.fd = open(path, flags, perms);
  62.     if (fas.fd < 0) return NULL;
  63.  
  64.     /* is this file brand new? */
  65.     end = lseek(fas.fd, 0, SEEK_END);
  66.     if (!end) {
  67.     newHdr.magic = FA_MAGIC;
  68.     newHdr.firstFree = 0;
  69.     if (write(fas.fd, &newHdr, sizeof(newHdr)) != sizeof(newHdr)) {
  70.         close(fas.fd);
  71.         return NULL;
  72.     }
  73.     fas.firstFree = 0;
  74.     fas.fileSize = sizeof(newHdr);
  75.     }
  76.     else {
  77.     lseek(fas.fd, 0, SEEK_SET);
  78.     if (read(fas.fd, &newHdr, sizeof(newHdr)) != sizeof(newHdr)) {
  79.         close(fas.fd);
  80.         return NULL;
  81.     }
  82.     if (newHdr.magic != FA_MAGIC) {
  83.         close(fas.fd);
  84.         return NULL;
  85.     }
  86.     fas.firstFree = newHdr.firstFree;
  87.  
  88.     if (lseek(fas.fd, 0, SEEK_END) < 0) {
  89.         close(fas.fd);
  90.         return NULL;
  91.     }
  92.     
  93.     fas.fileSize = lseek(fas.fd, 0, SEEK_CUR);
  94.     }
  95.  
  96.     fa = malloc(sizeof(*fa));
  97.     if (fa) *fa = fas;
  98.  
  99.     return fa;
  100. }
  101.  
  102. unsigned int faAlloc(faFile fa, unsigned int size) { /* returns 0 on failure */
  103.     unsigned int nextFreeBlock;
  104.     unsigned int newBlockOffset;
  105.     unsigned int footerOffset;
  106.     int failed = 0;
  107.     struct faFileHeader faHeader;
  108.     struct faHeader header, origHeader;
  109.     struct faHeader * restoreHeader = NULL;
  110.     struct faHeader nextFreeHeader, origNextFreeHeader;
  111.     struct faHeader * restoreNextHeader = NULL;
  112.     struct faHeader prevFreeHeader, origPrevFreeHeader;
  113.     struct faHeader * restorePrevHeader = NULL;
  114.     struct faFooter footer, origFooter;
  115.     struct faFooter * restoreFooter = NULL;
  116.     int updateHeader = 0;
  117.  
  118.     /* our internal idea of size includes overhead */
  119.     size += sizeof(struct faHeader) + sizeof(struct faFooter);
  120.  
  121.     /* Make sure they are allocing multiples of 64 bytes. It'll keep
  122.        things less fragmented that way */
  123.     (size % 64) ? size += (64 - (size % 64)) : 0;
  124.  
  125.     /* find a block via first fit - see Knuth vol 1 for why */
  126.     /* XXX this could be optimized a bit still */
  127.  
  128.     nextFreeBlock =  fa->firstFree;
  129.     newBlockOffset = 0;
  130.  
  131.     while (nextFreeBlock && !newBlockOffset) {
  132.     if (lseek(fa->fd, nextFreeBlock, SEEK_SET) < 0) return 0;
  133.     if (read(fa->fd, &header, sizeof(header)) != sizeof(header)) return 0;
  134.  
  135.     if (!header.isFree) {
  136.         fprintf(stderr, "free list corrupt (%d)- contact "
  137.             "support@redhat.com\n", nextFreeBlock);
  138.         exit(1);
  139.     }
  140.  
  141.     if (header.size >= size) {
  142.         newBlockOffset = nextFreeBlock;
  143.     } else {
  144.         nextFreeBlock = header.freeNext;
  145.     }
  146.     }
  147.  
  148.     if (newBlockOffset) {
  149.     /* header should still be good from the search */
  150.     origHeader = header;
  151.  
  152.     footerOffset = newBlockOffset + header.size - sizeof(footer);
  153.  
  154.     if (lseek(fa->fd, footerOffset, SEEK_SET) < 0) return 0;
  155.     if (read(fa->fd, &footer, sizeof(footer)) != sizeof(footer)) 
  156.         return 0;
  157.     origFooter = footer;
  158.  
  159.     /* should we split this block into two? */
  160.     /* XXX implement fragment creation here */
  161.  
  162.     footer.isFree = header.isFree = 0;
  163.  
  164.     /* remove it from the free list before */
  165.     if (newBlockOffset == fa->firstFree) {
  166.         faHeader.magic = FA_MAGIC;
  167.         faHeader.firstFree = header.freeNext;
  168.         fa->firstFree = header.freeNext;
  169.         updateHeader = 1;
  170.     } else {
  171.         if (lseek(fa->fd, header.freePrev, SEEK_SET) < 0) return 0;
  172.         if (read(fa->fd, &prevFreeHeader, sizeof(prevFreeHeader)) !=
  173.              sizeof(prevFreeHeader)) 
  174.         return 0;
  175.         origPrevFreeHeader = prevFreeHeader;
  176.  
  177.         prevFreeHeader.freeNext = header.freeNext;
  178.     }
  179.  
  180.     /* and after */
  181.     if (header.freeNext) {
  182.         if (lseek(fa->fd, header.freeNext, SEEK_SET) < 0) return 0;
  183.         if (read(fa->fd, &nextFreeHeader, sizeof(nextFreeHeader)) !=
  184.              sizeof(nextFreeHeader)) 
  185.         return 0;
  186.         origNextFreeHeader = nextFreeHeader;
  187.  
  188.         nextFreeHeader.freePrev = header.freePrev;
  189.     }
  190.  
  191.     /* if any of these fail, try and restore everything before leaving */
  192.     if (updateHeader) {
  193.         if (lseek(fa->fd, 0, SEEK_SET) < 0) 
  194.         return 0;
  195.         else if (write(fa->fd, &faHeader, sizeof(faHeader)) !=
  196.                  sizeof(faHeader)) 
  197.         return 0;
  198.     } else {
  199.         if (lseek(fa->fd, header.freePrev, SEEK_SET) < 0)
  200.         return 0;
  201.         else if (write(fa->fd, &prevFreeHeader, sizeof(prevFreeHeader)) !=
  202.              sizeof(prevFreeHeader))
  203.         return 0;
  204.         restorePrevHeader = &origPrevFreeHeader;
  205.     }
  206.  
  207.     if (header.freeNext) {
  208.         if (lseek(fa->fd, header.freeNext, SEEK_SET) < 0)
  209.         return 0;
  210.         else if (write(fa->fd, &nextFreeHeader, sizeof(nextFreeHeader)) !=
  211.              sizeof(nextFreeHeader))
  212.         return 0;
  213.  
  214.         restoreNextHeader = &origNextFreeHeader;
  215.     }
  216.  
  217.     if (!failed) {
  218.         if (lseek(fa->fd, newBlockOffset, SEEK_SET) < 0) 
  219.         failed = 1;
  220.         else if (write(fa->fd, &header, sizeof(header)) !=
  221.              sizeof(header)) {
  222.         failed = 1;
  223.         restoreHeader = &origHeader;
  224.         }
  225.     }
  226.  
  227.     if (!failed) {
  228.         if (lseek(fa->fd, footerOffset, SEEK_SET) < 0) 
  229.         failed = 1;
  230.         else if (write(fa->fd, &footer, sizeof(footer)) !=
  231.              sizeof(footer)) {
  232.         failed = 1;
  233.         restoreFooter = &origFooter;
  234.         }
  235.     }
  236.  
  237.     if (failed) {
  238.         if (updateHeader) {
  239.         faHeader.firstFree = newBlockOffset;
  240.         fa->firstFree = newBlockOffset;
  241.             lseek(fa->fd, 0, SEEK_SET);
  242.             write(fa->fd, &faHeader, sizeof(faHeader));
  243.         } 
  244.  
  245.         if (restorePrevHeader) {
  246.             lseek(fa->fd, header.freePrev, SEEK_SET);
  247.             write(fa->fd, restorePrevHeader, sizeof(*restorePrevHeader));
  248.         }
  249.  
  250.         if (restoreNextHeader) {
  251.             lseek(fa->fd, header.freeNext, SEEK_SET);
  252.             write(fa->fd, restoreNextHeader, sizeof(*restoreNextHeader));
  253.         }
  254.  
  255.         if (restoreHeader) {
  256.             lseek(fa->fd, newBlockOffset, SEEK_SET);
  257.             write(fa->fd, restoreHeader, sizeof(header));
  258.         }
  259.  
  260.         if (restoreFooter) {
  261.             lseek(fa->fd, footerOffset, SEEK_SET);
  262.             write(fa->fd, restoreFooter, sizeof(footer));
  263.         }
  264.  
  265.         return 0;
  266.     }
  267.     } else {
  268.     char * space;
  269.  
  270.     /* make a new block */
  271.     newBlockOffset = fa->fileSize;
  272.     footerOffset = newBlockOffset + size - sizeof(footer);
  273.  
  274.     space = alloca(size);
  275.     if (!space) return 0;
  276.  
  277.     footer.isFree = header.isFree = 0;
  278.     footer.size = header.size = size;
  279.     header.freePrev = header.freeNext = 0;
  280.  
  281.     /* reserve all space up front */
  282.         lseek(fa->fd, newBlockOffset, SEEK_SET);
  283.     if (write(fa->fd, space, size) != size) {
  284.         return 0;
  285.     }
  286.  
  287.         lseek(fa->fd, newBlockOffset, SEEK_SET);
  288.     if (write(fa->fd, &header, sizeof(header)) != sizeof(header)) {
  289.         return 0;
  290.     }
  291.  
  292.         lseek(fa->fd, footerOffset, SEEK_SET);
  293.     if (write(fa->fd, &footer, sizeof(footer)) != sizeof(footer)) {
  294.         return 0;
  295.     }
  296.  
  297.     fa->fileSize += size;
  298.     }
  299.     
  300.     return newBlockOffset + sizeof(header); 
  301. }
  302.  
  303. void faFree(faFile fa, unsigned int offset) {
  304.     struct faHeader header;
  305.     struct faFooter footer;
  306.     int footerOffset;
  307.     int prevFreeOffset, nextFreeOffset;
  308.     struct faHeader prevFreeHeader, nextFreeHeader;
  309.     struct faFileHeader faHeader;
  310.  
  311.     /* any errors cause this to die, and thus result in lost space in the
  312.        database. which is at least better then corruption */
  313.  
  314.     offset -= sizeof(header);
  315.  
  316.     /* find out where in the (sorted) free list to put this */
  317.     prevFreeOffset = fa->firstFree;
  318.  
  319.     if (!prevFreeOffset || (prevFreeOffset > offset)) {
  320.     nextFreeOffset = fa->firstFree;
  321.     prevFreeOffset = 0;
  322.     } else {
  323.     if (lseek(fa->fd, prevFreeOffset, SEEK_SET) < 0) return;
  324.     if (read(fa->fd, &prevFreeHeader, sizeof(prevFreeHeader)) != 
  325.         sizeof(prevFreeHeader)) return;
  326.  
  327.     while (prevFreeHeader.freeNext && prevFreeHeader.freeNext < offset) {
  328.         prevFreeOffset = prevFreeHeader.freeNext;
  329.         if (lseek(fa->fd, prevFreeOffset, SEEK_SET) < 0) return;
  330.         if (read(fa->fd, &prevFreeHeader, sizeof(prevFreeHeader)) != 
  331.             sizeof(prevFreeHeader)) return;
  332.     } 
  333.  
  334.     nextFreeOffset = prevFreeHeader.freeNext;
  335.     }
  336.  
  337.     if (nextFreeOffset) {
  338.     if (lseek(fa->fd, nextFreeOffset, SEEK_SET) < 0) return;
  339.     if (read(fa->fd, &nextFreeHeader, sizeof(nextFreeHeader)) != 
  340.         sizeof(nextFreeHeader)) return;
  341.     }
  342.  
  343.     if (lseek(fa->fd, offset, SEEK_SET) < 0)
  344.     return;
  345.     if (read(fa->fd, &header, sizeof(header)) != sizeof(header))
  346.     return;
  347.  
  348.     footerOffset = offset + header.size - sizeof(footer);
  349.  
  350.     if (lseek(fa->fd, footerOffset, SEEK_SET) < 0)
  351.     return;
  352.     if (read(fa->fd, &footer, sizeof(footer)) != sizeof(footer))
  353.     return;
  354.  
  355.     header.isFree = 1;
  356.     header.freeNext = nextFreeOffset;
  357.     header.freePrev = prevFreeOffset;
  358.     footer.isFree = 1;
  359.  
  360.     lseek(fa->fd, offset, SEEK_SET);
  361.     write(fa->fd, &header, sizeof(header));
  362.  
  363.     lseek(fa->fd, footerOffset, SEEK_SET);
  364.     write(fa->fd, &footer, sizeof(footer));
  365.  
  366.     if (nextFreeOffset) {
  367.     nextFreeHeader.freePrev = offset;
  368.     if (lseek(fa->fd, nextFreeOffset, SEEK_SET) < 0) return;
  369.     if (write(fa->fd, &nextFreeHeader, sizeof(nextFreeHeader)) != 
  370.         sizeof(nextFreeHeader)) return;
  371.     }
  372.  
  373.     if (prevFreeOffset) {
  374.     prevFreeHeader.freeNext = offset;
  375.     if (lseek(fa->fd, prevFreeOffset, SEEK_SET) < 0) return;
  376.     write(fa->fd, &prevFreeHeader, sizeof(prevFreeHeader));
  377.     } else {
  378.     fa->firstFree = offset;
  379.  
  380.     faHeader.magic = FA_MAGIC;
  381.     faHeader.firstFree = fa->firstFree;
  382.  
  383.     if (lseek(fa->fd, 0, SEEK_SET) < 0) return;
  384.     write(fa->fd, &faHeader, sizeof(faHeader));
  385.     }
  386. }
  387.  
  388. void faClose(faFile fa) {
  389.     close(fa->fd);
  390.     free(fa);
  391. }
  392.  
  393. int faFirstOffset(faFile fa) {
  394.     return faNextOffset(fa, 0);
  395. }
  396.  
  397. int faNextOffset(faFile fa, unsigned int lastOffset) {
  398.     struct faHeader header;
  399.     int offset;
  400.  
  401.     if (lastOffset) {
  402.     offset = lastOffset - sizeof(header);
  403.     } else {
  404.     offset = sizeof(struct faFileHeader);
  405.     }
  406.  
  407.     if (offset >= fa->fileSize) return 0;
  408.  
  409.     lseek(fa->fd, offset, SEEK_SET);
  410.     if (read(fa->fd, &header, sizeof(header)) != sizeof(header)) {
  411.     return 0;
  412.     }
  413.     if (!lastOffset && !header.isFree) return (offset + sizeof(header));
  414.  
  415.     do {
  416.     offset += header.size;
  417.  
  418.     lseek(fa->fd, offset, SEEK_SET);
  419.     if (read(fa->fd, &header, sizeof(header)) != sizeof(header)) {
  420.         return 0;
  421.     }
  422.  
  423.     if (!header.isFree) break;
  424.     } while (offset < fa->fileSize && header.isFree);
  425.  
  426.     if (offset < fa->fileSize) {
  427.     /* Sanity check this to make sure we're not going in loops */
  428.     offset += sizeof(header);
  429.  
  430.     if (offset <= lastOffset) return -1;
  431.  
  432.     return offset;
  433.     } else
  434.     return 0;
  435. }
  436.