Main Page   Modules   Compound List   File List   Compound Members   File Members   Related Pages  

lib/falloc.c

Go to the documentation of this file.
00001 
00014 #include "system.h"
00015 #include <rpmio_internal.h>
00016 #include <rpmerr.h>
00017 #include "falloc.h"
00018 #include "debug.h"
00019 
00022 #define FA_MAGIC      0x02050920
00023 
00024 struct faFileHeader {
00025     unsigned int magic;
00026     unsigned int firstFree;
00027 };
00028 
00029 struct faHeader {
00030     unsigned int size;                          
00031     unsigned int freeNext; /* offset of the next free block, 0 if none */
00032     unsigned int freePrev; 
00033     unsigned int isFree;
00034 
00035     /* note that the u16's appear last for alignment/space reasons */
00036 };
00037 
00038 struct faFooter {
00039     unsigned int size;
00040     unsigned int isFree; 
00041 } ;
00042 
00043 /* =============================================================== */
00044 static struct FDIO_s fadio_s = {
00045   NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
00046   fadOpen, NULL, NULL,  NULL, NULL, NULL, NULL, NULL, NULL
00047 };
00048 FDIO_t fadio = /*@-compmempass@*/ &fadio_s /*@=compmempass@*/ ;
00049 /* =============================================================== */
00050 
00051 /* flags are the same as for open(2) - NULL returned on error */
00052 FD_t fadOpen(const char * path, int flags, mode_t perms)
00053 {
00054     struct faFileHeader newHdr;
00055     FD_t fd;
00056 
00057     if (flags & O_WRONLY)
00058         return NULL;
00059 
00060     fd = ufdio->_open(path, flags, perms);
00061     if (Ferror(fd))
00062         /* XXX Fstrerror */
00063         return NULL;
00064 
00065     memcpy(fadio, fdio, sizeof(*fadio));
00066     fadio->_open = fadOpen;
00067 
00068     fdSetIo(fd, fadio);
00069     fadSetFirstFree(fd, 0);
00070     fadSetFileSize(fd, Fseek(fd, 0, SEEK_END));
00071 
00072     /* is this file brand new? */
00073     if (fadGetFileSize(fd) == 0) {
00074         newHdr.magic = FA_MAGIC;
00075         newHdr.firstFree = 0;
00076         if (Fwrite(&newHdr, sizeof(char), sizeof(newHdr), fd) != sizeof(newHdr)) {
00077             Fclose(fd);
00078             return NULL;
00079         }
00080         fadSetFirstFree(fd, 0);
00081         fadSetFileSize(fd, sizeof(newHdr));
00082     } else {
00083         if (Pread(fd, &newHdr, sizeof(newHdr), 0) != sizeof(newHdr)) {
00084             Fclose(fd);
00085             return NULL;
00086         }
00087         if (newHdr.magic != FA_MAGIC) {
00088             Fclose(fd);
00089             return NULL;
00090         }
00091         fadSetFirstFree(fd, newHdr.firstFree);
00092         fadSetFileSize(fd, Fseek(fd, 0, SEEK_END));
00093 
00094         if (fadGetFileSize(fd) < 0) {
00095             Fclose(fd);
00096             return NULL;
00097         }
00098     }
00099 
00100     /*@-refcounttrans@*/ return fd /*@=refcounttrans@*/ ;
00101 }
00102 
00103 /* returns 0 on failure */
00104 unsigned int fadAlloc(FD_t fd, unsigned int size)
00105 {
00106     unsigned int nextFreeBlock;
00107     unsigned int newBlockOffset;
00108     unsigned int footerOffset;
00109     int failed = 0;
00110     struct faFileHeader faHeader;
00111     struct faHeader header, origHeader;
00112     struct faHeader * restoreHeader = NULL;
00113     struct faHeader nextFreeHeader, origNextFreeHeader;
00114     struct faHeader * restoreNextHeader = NULL;
00115     struct faHeader prevFreeHeader, origPrevFreeHeader;
00116     struct faHeader * restorePrevHeader = NULL;
00117     struct faFooter footer, origFooter;
00118     struct faFooter * restoreFooter = NULL;
00119     int updateHeader = 0;
00120 
00121     memset(&header, 0, sizeof(header));
00122 
00123     /* our internal idea of size includes overhead */
00124     size += sizeof(struct faHeader) + sizeof(struct faFooter);
00125 
00126     /* Make sure they are allocing multiples of 64 bytes. It'll keep
00127        things less fragmented that way */
00128     (size % 64) ? size += (64 - (size % 64)) : 0;
00129 
00130     /* find a block via first fit - see Knuth vol 1 for why */
00131     /* XXX this could be optimized a bit still */
00132 
00133     nextFreeBlock = fadGetFirstFree(fd);
00134     newBlockOffset = 0;
00135 
00136     while (nextFreeBlock && !newBlockOffset) {
00137         if (Pread(fd, &header, sizeof(header), nextFreeBlock) != sizeof(header)) return 0;
00138 
00139 /* XXX W2DO? exit(EXIT_FAILURE) forces the user to discover rpm --rebuilddb */
00140         if (!header.isFree) {
00141             rpmError(RPMERR_FREELIST, _("free list corrupt (%u)- please run\n"
00142                         "\t\"rpm --rebuilddb\"\n"
00143                         "More information is available from http://www.rpm.org "
00144                         "or the rpm-list@redhat.com mailing list\n"
00145                         "if \"rpm --rebuilddb\" fails to correct the problem.\n"),
00146                         nextFreeBlock);
00147 
00148             exit(EXIT_FAILURE);
00149             /*@notreached@*/
00150         }
00151 
00152         if (header.size >= size) {
00153             newBlockOffset = nextFreeBlock;
00154         } else {
00155             nextFreeBlock = header.freeNext;
00156         }
00157     }
00158 
00159     if (newBlockOffset) {
00160         /* header should still be good from the search */
00161         origHeader = header;
00162 
00163         footerOffset = newBlockOffset + header.size - sizeof(footer);
00164 
00165         if (Pread(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer)) 
00166             return 0;
00167         origFooter = footer;
00168 
00169         /* should we split this block into two? */
00170         /* XXX implement fragment creation here */
00171 
00172         footer.isFree = header.isFree = 0;
00173 
00174         /* remove it from the free list before */
00175         if (newBlockOffset == fadGetFirstFree(fd)) {
00176             faHeader.magic = FA_MAGIC;
00177             faHeader.firstFree = header.freeNext;
00178             fadSetFirstFree(fd, header.freeNext);
00179             updateHeader = 1;
00180         } else {
00181             if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
00182                         header.freePrev) != sizeof(prevFreeHeader)) 
00183                 return 0;
00184             origPrevFreeHeader = prevFreeHeader;
00185 
00186             prevFreeHeader.freeNext = header.freeNext;
00187         }
00188 
00189         /* and after */
00190         if (header.freeNext) {
00191             if (Pread(fd, &nextFreeHeader, sizeof(nextFreeHeader),
00192                         header.freeNext) != sizeof(nextFreeHeader)) 
00193                 return 0;
00194             origNextFreeHeader = nextFreeHeader;
00195 
00196             nextFreeHeader.freePrev = header.freePrev;
00197         }
00198 
00199         /* if any of these fail, try and restore everything before leaving */
00200         if (updateHeader) {
00201             if (Pwrite(fd, &faHeader, sizeof(faHeader), 0) !=
00202                              sizeof(faHeader)) 
00203                 return 0;
00204         } else {
00205             if (Pwrite(fd, &prevFreeHeader, sizeof(prevFreeHeader),
00206                         header.freePrev) != sizeof(prevFreeHeader))
00207                 return 0;
00208             restorePrevHeader = &origPrevFreeHeader;
00209         }
00210 
00211         if (header.freeNext) {
00212             if (Pwrite(fd, &nextFreeHeader, sizeof(nextFreeHeader),
00213                         header.freeNext) != sizeof(nextFreeHeader))
00214                 return 0;
00215 
00216             restoreNextHeader = &origNextFreeHeader;
00217         }
00218 
00219         if (!failed) {
00220             if (Pwrite(fd, &header, sizeof(header), newBlockOffset) !=
00221                          sizeof(header)) {
00222                 failed = 1;
00223                 restoreHeader = &origHeader;
00224             }
00225         }
00226 
00227         if (!failed) {
00228             if (Pwrite(fd, &footer, sizeof(footer),
00229                         footerOffset) != sizeof(footer)) {
00230                 failed = 1;
00231                 restoreFooter = &origFooter;
00232             }
00233         }
00234 
00235         if (failed) {
00236             if (updateHeader) {
00237                 faHeader.firstFree = newBlockOffset;
00238                 fadSetFirstFree(fd, newBlockOffset);
00239                 (void)Pwrite(fd, &faHeader, sizeof(faHeader), 0);
00240             } 
00241 
00242             if (restorePrevHeader)
00243                 (void)Pwrite(fd, restorePrevHeader, sizeof(*restorePrevHeader),
00244                                 header.freePrev);
00245 
00246             if (restoreNextHeader)
00247                 (void)Pwrite(fd, restoreNextHeader, sizeof(*restoreNextHeader),
00248                                 header.freeNext);
00249 
00250             if (restoreHeader)
00251                 (void)Pwrite(fd, restoreHeader, sizeof(header),
00252                                 newBlockOffset);
00253 
00254             if (restoreFooter)
00255                 (void)Pwrite(fd, restoreFooter, sizeof(footer),
00256                                 footerOffset);
00257 
00258             return 0;
00259         }
00260     } else {
00261         char * space;
00262 
00263         /* make a new block */
00264         newBlockOffset = fadGetFileSize(fd);
00265         footerOffset = newBlockOffset + size - sizeof(footer);
00266 
00267         space = alloca(size);
00268         if (space == NULL) return 0;
00269         memset(space, 0, size);
00270 
00271         footer.isFree = header.isFree = 0;
00272         footer.size = header.size = size;
00273         header.freePrev = header.freeNext = 0;
00274 
00275         /* reserve all space up front */
00276         /* XXX TODO: check max. no. of bytes to write */
00277         if (Pwrite(fd, space, size, newBlockOffset) != size)
00278             return 0;
00279 
00280         if (Pwrite(fd, &header, sizeof(header), newBlockOffset) != sizeof(header))
00281             return 0;
00282 
00283         if (Pwrite(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer))
00284             return 0;
00285 
00286         fadSetFileSize(fd, fadGetFileSize(fd) + size);
00287     }
00288     
00289     return newBlockOffset + sizeof(header); 
00290 }
00291 
00292 void fadFree(FD_t fd, unsigned int offset)
00293 {
00294     struct faHeader header;
00295     struct faFooter footer;
00296     int footerOffset;
00297     int prevFreeOffset, nextFreeOffset;
00298     struct faHeader prevFreeHeader, nextFreeHeader;
00299     struct faFileHeader faHeader;
00300 
00301     /* any errors cause this to die, and thus result in lost space in the
00302        database. which is at least better then corruption */
00303 
00304     offset -= sizeof(header);
00305 
00306     /* find out where in the (sorted) free list to put this */
00307     prevFreeOffset = fadGetFirstFree(fd);
00308 
00309     if (!prevFreeOffset || (prevFreeOffset > offset)) {
00310         nextFreeOffset = fadGetFirstFree(fd);
00311         prevFreeOffset = 0;
00312     } else {
00313         if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
00314                         prevFreeOffset) != sizeof(prevFreeHeader))
00315             return;
00316 
00317         while (prevFreeHeader.freeNext && prevFreeHeader.freeNext < offset) {
00318             prevFreeOffset = prevFreeHeader.freeNext;
00319             if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
00320                         prevFreeOffset) != sizeof(prevFreeHeader))
00321                 return;
00322         } 
00323 
00324         nextFreeOffset = prevFreeHeader.freeNext;
00325     }
00326 
00327     if (nextFreeOffset) {
00328         if (Pread(fd, &nextFreeHeader, sizeof(nextFreeHeader),
00329                         nextFreeOffset) != sizeof(nextFreeHeader))
00330             return;
00331     }
00332 
00333     if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
00334         return;
00335 
00336     footerOffset = offset + header.size - sizeof(footer);
00337 
00338     if (Pread(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer))
00339         return;
00340 
00341     header.isFree = 1;
00342     header.freeNext = nextFreeOffset;
00343     header.freePrev = prevFreeOffset;
00344     footer.isFree = 1;
00345 
00346     /* XXX TODO: set max. no. of bytes to write */
00347     (void)Pwrite(fd, &header, sizeof(header), offset);
00348 
00349     (void)Pwrite(fd, &footer, sizeof(footer), footerOffset);
00350 
00351     if (nextFreeOffset) {
00352         nextFreeHeader.freePrev = offset;
00353         if (Pwrite(fd, &nextFreeHeader, sizeof(nextFreeHeader),
00354                         nextFreeOffset) != sizeof(nextFreeHeader))
00355             return;
00356     }
00357 
00358     if (prevFreeOffset) {
00359         prevFreeHeader.freeNext = offset;
00360         if (Pwrite(fd, &prevFreeHeader, sizeof(prevFreeHeader),
00361                         prevFreeOffset) != sizeof(prevFreeHeader))
00362             return;
00363     } else {
00364         fadSetFirstFree(fd, offset);
00365 
00366         faHeader.magic = FA_MAGIC;
00367         faHeader.firstFree = fadGetFirstFree(fd);
00368 
00369         /* XXX TODO: set max. no. of bytes to write */
00370         if (Pwrite(fd, &faHeader, sizeof(faHeader), 0) != sizeof(faHeader))
00371             return;
00372     }
00373 }
00374 
00375 int fadFirstOffset(FD_t fd)
00376 {
00377     return fadNextOffset(fd, 0);
00378 }
00379 
00380 int fadNextOffset(FD_t fd, unsigned int lastOffset)
00381 {
00382     struct faHeader header;
00383     int offset;
00384 
00385     offset = (lastOffset)
00386         ? (lastOffset - sizeof(header))
00387         : sizeof(struct faFileHeader);
00388 
00389     if (offset >= fadGetFileSize(fd))
00390         return 0;
00391 
00392     if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
00393         return 0;
00394 
00395     if (!lastOffset && !header.isFree)
00396         return (offset + sizeof(header));
00397 
00398     do {
00399         offset += header.size;
00400 
00401         if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
00402             return 0;
00403 
00404         if (!header.isFree) break;
00405     } while (offset < fadGetFileSize(fd) && header.isFree);
00406 
00407     if (offset < fadGetFileSize(fd)) {
00408         /* Sanity check this to make sure we're not going in loops */
00409         offset += sizeof(header);
00410 
00411         if (offset <= lastOffset) return -1;
00412 
00413         return offset;
00414     } else
00415         return 0;
00416 }

Generated at Mon May 21 08:53:39 2001 for rpm by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001