// @(#)root/net:$Name:  $:$Id: TCache.cxx,v 1.7 2004/01/19 18:31:13 rdm Exp $
// Author: Fons Rademakers   13/01/2001

/*************************************************************************
 * Copyright (C) 1995-2001, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TCache                                                               //
//                                                                      //
// A caching system to speed up network I/O, i.e. when there is         //
// no operating system caching support (like the buffer cache for       //
// local disk I/O). The cache makes sure that every I/O is done with    //
// a (large) fixed length buffer thereby avoiding many small I/O's.     //
// The default page size is 512KB. The cache size is not very important //
// when writing sequentially a file, since the pages will not be        //
// reused. In that case use a small cache containing 10 to 20 pages.    //
// In case a file is used for random-access the cache size should be    //
// taken much larger to avoid re-reading pages over the network.        //
// Notice that the TTree's have their own caching mechanism (see        //
// TTree::SetMaxVirtualSize()), so when using mainly TTree's with large //
// basket buffers the cache can be kept quite small.                    //
// Currently the TCache system is used by the classes TNetFile,         //
// TRFIOFile and TWebFile.                                              //
//                                                                      //
// Extra improvement would be to run the Free() process in a separate   //
// thread. Possible flush parameters:                                   //
// nfract  25   fraction of dirty buffers above which the flush process //
//              is activated                                            //
// ndirty  500  maximum number of buffer block which may be written     //
//              during a flush                                          //
//                                                                      //
//////////////////////////////////////////////////////////////////////////


#include "TCache.h"
#include "TSortedList.h"
#include "TFile.h"


ClassImp(TCache)

//______________________________________________________________________________
 TCache::TCache(Int_t maxCacheSize, TFile *file, Int_t pageSize)
{
   // Create a file cache. Mainly useful for remote files like TNetFile,
   // TWebFile and TRFIOFile where the local OS is not doing any caching.
   // The maxCacheSize is in MBytes and the pageSize is in bytes (default
   // being kDfltPageSize).

   if (!file) {
      Error("TCache", "no file specified");
      MakeZombie();
      return;
   }

   fFile      = file;
   fEOF       = fFile->GetSize();              // get initial file size
   fHighWater = maxCacheSize * 1024 * 1024;
   fLowWater  = fHighWater * kDfltLowLevel / 100;
   fLowLevel  = kDfltLowLevel;
   fRecursive = kFALSE;
   SetPageSize(pageSize);

   fCache = new TCacheList(Int_t(fHighWater/fPageSize/3));
   fNew   = new TSortedList;
   fFree  = new TList;
   fCache->SetOwner();
   fFree->SetOwner();
}

//______________________________________________________________________________
 TCache::~TCache()
{
   // Clean up cache.

   delete fCache;
   delete fNew;
   delete fFree;
}

//______________________________________________________________________________
 void TCache::SetPageSize(Int_t size)
{
   // Make sure the page size is a power of two, with a minimum of 4096.

   if (size < 4096) size = 4096;

   for (int i = 0; i < int(sizeof(size)*8); i++)
      if ((size >> i) == 1) {
         fDiv = i;
         break;
      }

   fPageSize = 1 << fDiv;
}

//______________________________________________________________________________
TCache::TPage *TCache::ReadPage(Long64_t offset)
{
   // Read the page starting at offset in the cache and return the
   // page object. If there are no more free pages free pages up
   // to the low water mark. The freed pages are the least recently
   // used pages (lru) which are at the head of the fCache hash list.
   // Returns 0 in case of error.

   fRecursive = kTRUE;

   // check if there is a free page object in the free list and use that
   if (fFree->GetSize() > 0) {
      TPage *p = (TPage*) fFree->First();
      Int_t len = offset + fPageSize > fEOF ? Int_t(fEOF - offset) : fPageSize;
      if (len < 0) len = 0;
      if (len) fFile->Seek(offset);
      if (len && fFile->ReadBuffer(p->Data(), len)) {
         fRecursive = kFALSE;
         return 0;
      }
      p->fOffset = offset;
      p->fSize   = len;
      fFree->Remove(p);
      fCache->Add(p);
      fRecursive = kFALSE;
      return p;
   }

   // if cache is not full, create new page and use it
   if (ULong_t(fCache->GetSize() * fPageSize) < fHighWater) {
      char *data = new char[fPageSize];
      Int_t len = offset + fPageSize > fEOF ? Int_t(fEOF - offset) : fPageSize;
      if (len < 0) len = 0;
      if (len) fFile->Seek(offset);
      if (len && fFile->ReadBuffer(data, len)) {
         fRecursive = kFALSE;
         return 0;
      }
      TPage *p = new TPage(offset, data, len);
      fCache->Add(p);
      fRecursive = kFALSE;
      return p;
   }

   // if we come here there are no free pages and the cache is full, free
   // pages up to low water mark
   if (Free(fLowWater) < 0) {
      fRecursive = kFALSE;
      return 0;
   }

   return ReadPage(offset);
}

//______________________________________________________________________________
 Int_t TCache::ReadBuffer(Long64_t offset, char *buf, Int_t len)
{
   // Return in buf len bytes starting at offset. Returns < 0 in
   // case of error, 0 in case ReadBuffer() was recursively called
   // via ReadPage() and 1 in case of success.

   if (fRecursive) return 0;

   // Find in which page offset is located
   Long64_t pageoffset = (offset >> fDiv) << fDiv;  // offset & ~(fPageSize-1)
   Int_t  begin = Int_t(offset & (fPageSize-1));
   Long_t boff  = 0;

   do {
      Int_t blen = begin+len>fPageSize ? fPageSize-begin : len;
      TPage t(pageoffset, 0, 0);
      TPage *p = (TPage*) fCache->FindObject(&t);
      if (p) {
         // found page in cache, copy to buf
         memcpy(buf+boff, p->Data()+begin, blen);
         fCache->PageUsed(p);
      } else {
         // read page in cache and copy to buf
         p = ReadPage(pageoffset);
         if (p)
            memcpy(buf+boff, p->Data()+begin, blen);
         else
            return -1;
      }
      boff       += blen;
      len        -= blen;
      pageoffset += fPageSize;
      begin       = 0;
   } while (len > 0);

   return 1;
}

//______________________________________________________________________________
 Int_t TCache::WritePage(TPage *page)
{
   // Write dirty page to file. Returns -1 in case of error.

   fRecursive = kTRUE;

   page->SetBit(TPage::kLocked);

   fFile->Seek(page->Offset());
   if (fFile->WriteBuffer(page->Data(), page->Size())) {
      page->ResetBit(TPage::kLocked);
      fRecursive = kFALSE;
      return -1;
   }

   if (page->Offset() + page->Size() > fEOF)
      fEOF = page->Offset() + page->Size();

   page->ResetBit(TPage::kDirty);
   page->ResetBit(TPage::kLocked);

   fRecursive = kFALSE;

   return 0;
}

//______________________________________________________________________________
 Int_t TCache::WriteBuffer(Long64_t offset, const char *buf, Int_t len)
{
   // Write a buffer to the cache. Returns < 0 in case of error, 0 in
   // case WriteBuffer() was recursively called via WritePage() and 1
   // in case of success.

   if (fRecursive) return 0;

   // Find in which page offset is located
   Long64_t pageoffset = (offset >> fDiv) << fDiv;  // offset & ~(fPageSize-1)
   Int_t  begin = Int_t(offset & (fPageSize-1));
   Long_t boff  = 0;

   do {
      Int_t blen = begin+len>fPageSize ? fPageSize-begin : len;
      TPage t(pageoffset, 0, 0);
      TPage *p = (TPage*) fCache->FindObject(&t);
      if (p) {
         // found page in cache, copy buf to it
         memcpy(p->Data()+begin, buf+boff, blen);
         if (p->fSize < begin+blen) {
            p->fSize = begin+blen;
            if (!fNew->Contains(p))
               fNew->Add(p);
         }
         p->SetBit(TPage::kDirty);
         fCache->PageUsed(p);
      } else {
         // read page in cache and copy buf to it
         p = ReadPage(pageoffset);
         if (p) {
            memcpy(p->Data()+begin, buf+boff, blen);
            if (p->fSize < begin+blen) {
               p->fSize = begin+blen;
               if (!fNew->Contains(p))
                  fNew->Add(p);
            }
            p->SetBit(TPage::kDirty);
         } else
            return -1;
      }
      boff       += blen;
      len        -= blen;
      pageoffset += fPageSize;
      begin       = 0;
   } while (len > 0);

   return 1;
}

//______________________________________________________________________________
 Int_t TCache::Free(ULong_t upto)
{
   // Free pages so that specified number of bytes remains in the cache.
   // Dirty pages are written to file. Returns < 0 in case of error
   // (typically when there was an error writing a dirty page).

   Int_t err;
   if ((err = FlushNew()) < 0)
      return err;

   while (ULong_t(fCache->GetSize() * fPageSize) > upto) {
      TPage *p = (TPage*) fCache->First();
      if (p->TestBit(TPage::kDirty)) {
         if ((err = WritePage(p)) < 0)
            return err;
      }
      fCache->Remove(p);
      fFree->Add(p);
   }
   return 0;
}

//______________________________________________________________________________
 Int_t TCache::FlushList(TList *list)
{
   // Flush all dirty pages in the specified list to file. Return < 0 in
   // case of error (typically when there was an error writing a dirty page).

   TIter next(list);
   TPage *p;
   while ((p = (TPage*) next())) {
      if (p->TestBit(TPage::kDirty)) {
         Int_t err;
         if ((err = WritePage(p)) < 0)
            return err;
      }
   }
   return 0;
}

//______________________________________________________________________________
 Int_t TCache::Flush()
{
   // Flush all dirty pages to file. Return < 0 in case of error
   // (typically when there was an error writing a dirty page).

   Int_t err;
   if ((err = FlushNew()) < 0)
      return err;
   if ((err = FlushList(fCache)) < 0)
      return err;

   return 0;
}

//______________________________________________________________________________
 Int_t TCache::FlushNew()
{
   // Flush all new pages to file. New pages are pages in the fNew list.
   // When a page is in this list it means that this page extends the file
   // (i.e. is adds new pages to the file). The issue with new pages is that
   // they need to be flushed in the right order. One can not write at an
   // offset past the EOF. Therefore the new pages are put in a sorted
   // list and then written in ascending fOffset order.

   Int_t err;
   if ((err = FlushList(fNew)) < 0)
      return err;

   fNew->Clear();

   return 0;
}

//______________________________________________________________________________
 Int_t TCache::Resize(Int_t maxCacheSize)
{
   // Resize the cache (either increase or decrease the size). Returns the
   // previous cache size or -1 in case of error. Input and output is in MB's.
   // Minimum cache size is 1 MB.

   if (maxCacheSize < 1) maxCacheSize = 1;

   ULong_t newSize = maxCacheSize * 1024 * 1024;
   Int_t   oldSize = Int_t(fHighWater / 1024 / 1024);

   if (newSize == fHighWater)
      return maxCacheSize;

   else if (newSize < fHighWater) {
      ULong_t inUse = (fCache->GetSize() + fFree->GetSize()) * fPageSize;
      if (inUse > newSize) {
         // first free active cache to not contain more than newSize,
         // then delete free pages up to desired new limit
         if (ULong_t(fCache->GetSize() * fPageSize) > newSize) {
            if (Free(newSize) < 0) {
               Error("Resize", "error freeing pages");
               return -1;
            }
            fFree->Delete();
         } else {
            while (inUse > newSize) {
               TPage *p = (TPage*) fFree->First();
               if (!p) break;
               fFree->Remove(p);
               delete p;
               inUse -= fPageSize;
            }
         }
      }
   }
   fHighWater = newSize;
   fLowWater  = fHighWater * fLowLevel / 100;
   return oldSize;
}

//______________________________________________________________________________
 Int_t TCache::GetActiveCacheSize() const
{
   // Get size of all allocated cache pages (in use and free pages).

   return Int_t(((fCache->GetSize()+fFree->GetSize())*fPageSize)/1024/1024);
}

//______________________________________________________________________________
 void TCache::SetLowLevel(Int_t percentOfHigh)
{
   // Set the low water level. This is in percent of the maxCacheSize.
   // When the cache is full it will be freed up to percentOfHigh. The
   // default is kDfltLowLevel=70%.

   fLowLevel = percentOfHigh;
   fLowWater = fHighWater * fLowLevel / 100;
}