Re: tape filling algorithm? (flush, or dump)

>>>On Wed, Nov 20, 2002 at 01:47:50PM -0600, Deb Baddorf wrote:
>>>> What kind of optimiaztion does amanda use while flushing
>>>> dumps to tape?
>>>>
>>>There is no optimazation, first in, first out.
>>>That's a need feature.
>>>
>>>Jean-Louis



Here's a basic algorithm  (in pseudo-code).
Is this useful to somebody who is already working on this code?
Or should I attempt to fit it into the actual   taper  code myself?

Deb Baddorf

=============================
This *should*  handle both the FLUSH case  (all data is available from
the start)   and the on-going AMDUMP case  (data is added as we go).
I may notice more errors but I think I got them all.

To "grok"  the basic algorithm  (ridiculously simple)   ignore
or white out the  "SPIN"  paragraphs which wait for more data to
arrive.
===========================================

stuff = collection of items to be put into knapsack.
       Dumpfiles in this case (includes tarfiles too)
Stuff is probably a doubly(?) linked list.  Operations required:
status = insert(item)
status = remove(ptr)  or maybe remove(item)
ptr = get_largest()
#boolean = is_empty()
boolean = has_data()     #opposite sense to   is_empty()

boolean = more_coming() #somebody elsewhere needs to tell us when no moredumps are coming down the pipe


item
number = size(item)
ptr = get_next_smaller()    # return item next smaller than self

(maybe should be a function of the COLLECTION instead of the item,for project OO code)

next_ptr     #if you use a doubly linked list
prev_ptr     #if you use a doubly linked list

string = get_name(item) ?? for the index, or some such. Maybe forerror message when dump won't fit.


knapsack    #(or,  tape!)
number = size_remaining()

status = add(item) # responsible to DELETE from holding disk aftersuccessful & from COLLECTION abovemake_full() # decree it "full" when no available items can fitin the remaining space

boolean = has_space()    # is not yet full


bunch-o-knapsacks   #(or,  how many tapes are available?)
ptr = gimme_one()
boolean = is_more()
==========================================

PACK_ALL_STUFF   #i.e.  start taping
{

mystuff = new stuff() # filled somewhere else, or here, but beforealgorithm below

allsacks = new bunch-o-knapsacks()  #number comes from   RUNTAPES parameter

    yada yada yada
    maybe twiddle thumbs till significant data arrives, if holding disk allows


while ( allsacks.is_more()       # stop when we run out of sacks (tapes)
        or  (not mystuff.has_data()     # or when we run out of data

and not mystuff.more_coming() ) ) # and know that no moreis coming

 {
   this_sack = allsacks.gimme_one()

   while ( not mystuff.has_data()  )   #wait for some data to arrive
         {spin
          check "more coming" in case a client dies
         }

while ( mystuff.has_data() and #there is still data waiting tobe taped

           this_sack.has_space() )             #the sack (tape) has room left
   {

#remember, in "timed" version, a bigger one may be added duringany pass#so, we start with biggest each time and add the first thatwill fit

      fill_sack (this_sack, mystuff.get_largest())

      while ( not mystuff.has_data()  )   #wait for some more data to arrive
         {spin
          check "more coming" in case a client dies
         }
   }
 }
}
==========================================
fill_sack(sackptr, item_ptr)
{
   if (item_ptr is NULL)         #there are no more smaller items
    {

sackptr.make_full() #decree sack (tape) to be full, so we canmove on to another

        return
    }

isize=item_ptr.size(); ssize=sackptr.size_remaining(); #store forpossible error msg#or assign to variable IN the if statement, but too messy todo in psuedo-code here!

if ( item_ptr.size() <= sackptr.size_remaining() ) #if item fits,according to sack specs,

     {                                                  #  put it in the sack

status = sackptr.add(item_ptr) # add MUST delete from holdingdisk, if it finishes successfully# add MUST also adjustsack's size_remaining value# it writes the INDEX, and doesother bookkeeping too# Also removes ITEM from "stuff"list of available dumps to flush

if ( not status) # failed -- tape size must've beenslightly wrong. That's life.

sackptr.make_full() # we've already written to EOT socan't try another size item

            write message "Sack(tape) wasn't as big as " isize + ssize.
            write message "May want to correct sack specs  (tapesize)"
         }

     }
   else     #find next smaller item and try that one
     {
        fill_sack (sackptr, item_ptr.get_next_smaller())
     }

}