[RC5] LIFO? Is this true?

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Mon May 11 12:14:22 EDT 1998


     Locking entire shared files is a terrible idea.  This locking 
     technique locks the entire buff-in down during a fetch or during a 
     "get a new block to crack".  Locking the entire file defeats the 
     advantage of multithreading the clients.  All clients that finish a 
     block during a fetch have to wait until the fetch is completed to 
     get a new block *even if the block they get isn't a newly fetched 
     one*.
     
     Clients "should" do record-level locking.  Unfortunately on MS OSes, 
     the finest OS-supported locking is one cluster which is much larger 
     than a block record in the buff-* files.  Other OSes don't seem to 
     have this idiotic limitation.
     
     Finally, a FIFO buff-* file doesn't require any data structure.  No 
     header is required because the number of blocks in the file can be 
     inferred directly from the file size.  There is no need for a 
     pointer to the end of the file because the end of the file is a 
     well-defined location easily reached in most streaming i/o packages, 
     like the built in support in C and C++.  Locking is only needed for 
     the end of the file, so *in principle*, a newly idled client can 
     fetch a block from the unlocked portion of the file while a fetching 
     client can append blocks to the file.
     
     Appending is a trivial operation in a lot of real filesystems.  
     Prepending is not.  Implementing the buff-* files as LIFOs was 
     trivial when the v1 and v2 clients were specified.  Implementing the 
     buff-* files as FIFOs would have required more development time 
     because verifying any code, even CompSci101 data structures, 
     requires more time than not having to verify it.  At the time this 
     architectural decision was made, time was better spent on other 
     endeavours.  Expecting that the v2 clients will change now that the 
     v2 specification is so well tested is folly.  v3 has been touted to 
     be FIFO (for RC5-64 and DES-x-y) (and there's some mild question as 
     to whether or not it will support LIFO, since I can imagine the v3 
     distributed filesystem working as named pipes instead of inert 
     storage, an implementation that would necessitate FIFO and make LIFO 
     require additional client code).
            -- Eric Gindrup ! gindrup at Okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: [RC5] LIFO?  Is this true? 
Author:  <rc5 at llamas.net> at SMTP
Date:    5/9/98 2:02 AM


Guys,
     
You are making FIFO too hard!  It's quite easy:
     
OK, in the BUFF-IN file, for LIFO (a stack), you need to have a file 
header, which contains the number of records in the file, file structure 
version info, a pointer to the next record (top of the stack), etc.  The 
pointer can be implied (i.e. it's always the last record in the file, etc).
 Then, you have a number of fixed-length records containing the RC5 block
info and a pointer to the next record (can be implied also - i.e. it's 
always "current record" minus one).  To get a block, you have to lock the 
file for exclusive access, read the fileheader, fetch the record indicated 
by the fileheader, update and write the fileheader back to the file, and 
finally unlock the file.  Adding a record to the file is similar.
     
For FIFO (a queue), it is almost as simple, but the fileheader contains 
three pointers.  A "front" pointer which points to the "first record in the 
list", a "back" pointer which points to the "last record in the list", and 
a "deleted" pointer which points to a linked list (a stack) of records that 
have been deleted and can now be reused.  So, when you get a record, you 
get from the "front" of the list, update the "front" pointer to point to 
the next record in the list, and add the current (just read) record to the 
"deleted" stack:
     
   //Find and read first-in-list record
   RN = FileHeader.QFront;  ReadRecord(RN,&Data);
     
   //Make use of information in the record 
   ... = Data.RC5Stuff;
     
   //Fix-up FileHeader and Deleted Record List 
   FileHeader.QFront = Data.NextRecord;
   if (FileHeader.QFront == 0) FileHeader.QBack = 0; 
   Data.NextRecord = FileHeader.DeletedRecordsList; 
   FileHeader.DeletedRecordsList = RN;
   WriteRecord(RN,&Data);
     
     
When you add a record, you use a record from the "deleted" stack (if empty, 
then add to end of file), point the current "back" record to this new 
record, and point the "back" pointer to this new record:
     
   //Compute the Record Number of the new record 
   if (FileHeader.DeletedRecordsList == 0) {
      //Deleted list is empty, add to end of file 
      NewRN = ++FileHeader.nRecords;
      }
   else {
      NewRN = FileHeader.DeletedRecordsList; 
      ReadRecord(NewRN,&Data);
      FileHeader.DeletedRecordsList = Data.NextRecord; 
      }
     
   //Initialize and store new record
   Data.RC5Stuff = ...;
   Data.Next = 0;
   WriteRecord(NewRN,&Data);
     
   //Fix-up FileHeader and previous end-of-list record
   if (FileHeader.QBack == 0) FileHeader.QBack = FileHeader.QFront = NewRN; 
   else {
      ReadRecord(FileHeader.QBack,&Data);
      Data.NextRecord = NewRN;
      WriteRecord(FileHeader.QBack,&Data); 
      FileHeader.QBack = NewRN;
      }
     
     
Anyway, it's basic Programming 101 - Linked-lists, Stacks, and Queues. 
Except using record numbers instead of memory addresses as pointers.
     
- Sanford
     
     
At 10:09 PM 5/7/1998 , Phil Gregory wrote:
>> Well... Most operating systems don't support LIFO either.  They support 
>> sequential reads/writes and positioning to a specific byte offset.  FIFO 
>> takes about 10 minutes of extra coding compared to LIFO.
>
>The problems are in what to do after you've finished a block and where new 
>blocks go.  After you've finished a LIFO block, you just move the file 
>pointer back to point to the block before it.  The finished block can be 
>discarded and/or ignored.  After you've finished a FIFO block, you either 
>move the file pointer forward and leave some dead space at the beginning 
>of the file or rewrite the entire file to remove the dead space.  The 
>latter obviously causes a performance hit, especially with large buff-ins. 
>The former, aside from being a really bad use of space, causes major 
>problems when new blocks are added.  When blocks are added, where are they 
>added?  LIFO always adds at the end--very easy.  FIFO rewriting the file 
>every time also adds them at the end of the file, but the constant 
>rewriting is bad anyway.  The other scenario for a FIFO either adds at 
>the end or the beginning.  If at the end, then the file keeps growing and 
>growing.  If at the beginning, what do you do if you have more blocks than 
>room for them?
>
>In short, LIFO is a lot easier to implement.  I'd rather that the coders 
>put their work into setting up v3 and keeping the creeping featureitis in 
>the current clients to a minimum.
     
     
     
At 10:29 AM 5/8/1998, Michael K. Weise wrote:
>The way I'd remove a block from a FIFO buffer is to fill it with zeros, then 
>compare total dead space to total file size and rewrite the entire file if 
>dead space exceeds 50%. 
     
     
     
At 12:24 PM 5/8/1998, R. Kelley Cook
>Or you can keep a separate 1 bits per block map to keep track of which 
>blocks have been loaded or checked plus each client keeps a pointer to 
>the current block and then you would run through the blocks in a 
>circular fashion.  This would have neither of your disadvantages and be 
>mostly FIFO.  
>
>Main difference in code would be the config file itself could not hold 
>the number of blocks to load, but this information could be easily 
>determined from the file itself.  If the filesize is zero then it 
>should autmatically run the initialization/resize routine would set up 
>the file.
>
>0 - empty and/or already checked and results placed in buff-out.rc5 
>1 - loaded but not completely checked
     
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net 
rc5-digest subscribers replace rc5 with rc5-digest
     
     

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list