degate  0.1.2
TileCache.h
Go to the documentation of this file.
00001 /* -*-c++-*-
00002 
00003  This file is part of the IC reverse engineering tool degate.
00004 
00005  Copyright 2008, 2009, 2010 by Martin Schobert
00006 
00007  Degate is free software: you can redistribute it and/or modify
00008  it under the terms of the GNU General Public License as published by
00009  the Free Software Foundation, either version 3 of the License, or
00010  any later version.
00011 
00012  Degate is distributed in the hope that it will be useful,
00013  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  GNU General Public License for more details.
00016 
00017  You should have received a copy of the GNU General Public License
00018  along with degate. If not, see <http://www.gnu.org/licenses/>.
00019 
00020 */
00021 
00022 #ifndef __TILECACHE_H__
00023 #define __TILECACHE_H__
00024 
00025 #include <MemoryMap.h>
00026 #include <FileSystem.h>
00027 #include <Configuration.h>
00028 
00029 #include <string>
00030 #include <map>
00031 #include <memory>
00032 #include <ctime>
00033 #include <utility> // for make_pair
00034 #include <iostream>
00035 
00036 #ifdef __APPLE__
00037   #include <sys/time.h> // for gettimeofday
00038   #define GET_CLOCK(dst_variable) \
00039   { \
00040       struct timeval tv; \
00041       gettimeofday(&tv, NULL); \
00042       dst_variable.tv_sec = tv.tv_sec; \
00043       dst_variable.tv_nsec = tv.tv_usec * 1000; \
00044   }
00045 #else
00046   #define GET_CLOCK(dst_variable) \
00047       clock_gettime(CLOCK_MONOTONIC,  &dst_variable);
00048 #endif
00049 
00050 // #define TILECACHE_DEBUG
00051 
00052 /**
00053  * Overloaded comparison operator for timespec-structs.
00054  * @return Returns true, if \p a is completely before \p b. Else
00055  *   false is returned.
00056  */
00057 static bool operator<(struct timespec const & a, struct timespec const & b) {
00058   if(a.tv_sec < b.tv_sec) return true;
00059   else if(a.tv_sec == b.tv_sec && a.tv_nsec < b.tv_nsec) return true;
00060   else return false;
00061 }
00062 
00063 namespace degate {
00064 
00065 
00066   class TileCacheBase {
00067   public:
00068     virtual void cleanup_cache() = 0;
00069     virtual void print() const = 0;
00070   };
00071 
00072   class GlobalTileCache : public SingletonBase<GlobalTileCache> {
00073 
00074     friend class SingletonBase<GlobalTileCache>;
00075 
00076   private:
00077 
00078     size_t max_cache_memory;
00079     size_t allocated_memory;
00080 
00081     typedef std::pair<struct timespec, size_t> cache_entry_t;
00082     typedef std::map<TileCacheBase *, cache_entry_t> cache_t;
00083 
00084     cache_t cache;
00085 
00086   private:
00087 
00088     GlobalTileCache() : allocated_memory(0) {
00089       Configuration & conf = Configuration::get_instance();
00090       max_cache_memory = conf.get_max_tile_cache_size() * 1024 *1024;
00091     }
00092 
00093     void remove_oldest() {
00094       struct timespec now;
00095       GET_CLOCK(now);
00096 
00097       TileCacheBase * oldest = NULL;
00098 
00099       for(cache_t::iterator iter = cache.begin(); iter != cache.end(); ++iter) {
00100         cache_entry_t & entry = iter->second;
00101         if(entry.first < now) {
00102           now.tv_sec = entry.first.tv_sec;
00103           now.tv_nsec = entry.first.tv_nsec;
00104           oldest = iter->first;
00105         }
00106       }
00107 
00108       if(oldest) {
00109 #ifdef TILECACHE_DEBUG
00110         debug(TM, "Will call cleanup on %p", oldest);
00111 #endif
00112         oldest->cleanup_cache();
00113       }
00114       else {
00115 #ifdef TILECACHE_DEBUG
00116         debug(TM, "there is nothing to free.");
00117         print_table();
00118 #endif
00119       }
00120     }
00121 
00122   public:
00123 
00124     void print_table() const {
00125       printf("Global Image Tile Cache:\n"
00126              "Used memory : %llu bytes\n"
00127              "Max memory  : %llu bytes\n\n"
00128              "Holder           | Last access (sec,nsec)    | Amount of memory\n"
00129              "-----------------+---------------------------+------------------------------------\n",
00130              (long long unsigned)allocated_memory, (long long unsigned)max_cache_memory);
00131 
00132       for(cache_t::const_iterator iter = cache.begin(); iter != cache.end(); ++iter) {
00133         cache_entry_t const& entry = iter->second;
00134         printf("%16p | %12ld.%12ld | %lu M (%lu bytes)\n",
00135                iter->first, entry.first.tv_sec, entry.first.tv_nsec, entry.second/(1024*1024), entry.second);
00136         iter->first->print();
00137       }
00138 
00139       printf("\n");
00140     }
00141 
00142     bool request_cache_memory(TileCacheBase * requestor, size_t amount) {
00143 
00144 #ifdef TILECACHE_DEBUG
00145       debug(TM, "Local cache %p requests %d bytes.", requestor, amount);
00146 #endif
00147       while(allocated_memory + amount > max_cache_memory) {
00148 #ifdef TILECACHE_DEBUG
00149         debug(TM, "Try to free memory");
00150 #endif
00151         remove_oldest();
00152       }
00153 
00154       if(allocated_memory + amount <= max_cache_memory) {
00155         struct timespec now;
00156         GET_CLOCK(now);
00157 
00158         cache_t::iterator found = cache.find(requestor);
00159         if(found == cache.end()) {
00160           cache[requestor] = std::make_pair(now, amount);
00161         }
00162         else {
00163           cache_entry_t & entry = found->second;
00164           entry.first.tv_sec = now.tv_sec;
00165           entry.first.tv_nsec = now.tv_nsec;
00166           entry.second += amount;
00167         }
00168 
00169         allocated_memory += amount;
00170 #ifdef TILECACHE_DEBUG
00171         print_table();
00172 #endif
00173         return true;
00174       }
00175 
00176       debug(TM, "Can't free memory.");
00177 
00178       print_table();
00179       return false;
00180     }
00181 
00182     void release_cache_memory(TileCacheBase * requestor, size_t amount) {
00183 
00184 #ifdef TILECACHE_DEBUG
00185       debug(TM, "Local cache %p releases %d bytes.", requestor, amount);
00186 #endif
00187 
00188       cache_t::iterator found = cache.find(requestor);
00189 
00190       if(found == cache.end()) {
00191         debug(TM, "Unknown memory should be released.");
00192         print_table();
00193         assert(1==0);
00194       }
00195       else {
00196         cache_entry_t & entry = found->second;
00197 
00198         if(entry.second >= amount) {
00199           entry.second -= amount;
00200           assert(allocated_memory >= amount);
00201           if(allocated_memory >= amount) allocated_memory -= amount;
00202           else {
00203             debug(TM, "More mem to release than available.");
00204             print_table();
00205             assert(1==0);
00206           }
00207         }
00208         else {
00209           print_table();
00210           assert(entry.second >= amount); // will break
00211         }
00212 
00213         if(entry.second == 0) {
00214 #ifdef TILECACHE_DEBUG
00215           debug(TM, "Memory completely released. Remove entry from global cache.");
00216 #endif
00217           cache.erase(found);
00218         }
00219       }
00220 
00221     }
00222 
00223   };
00224 
00225 
00226   /**
00227    * The TileCache class handles caching of image tiles.
00228    *
00229    * The implementation keeps track how old the cached tile is.
00230    * If new tiles become loaded, old tiles are removed from the
00231    * cache. You can control the numer of cached tiles via the
00232    * constructor parameter \p _min_cache_tiles. The memory
00233    * requirement is around
00234    * \p _min_cache_tiles*sizeof(PixelPolicy::pixel_type)*(2^_tile_width_exp)^2 ,
00235    * where \p sizeof(PixelPolicy::pixel_type) is the size of a pixel.
00236    */
00237 
00238   template<class PixelPolicy>
00239   class TileCache : public TileCacheBase {
00240 
00241     friend class GlobalTileCache;
00242 
00243   private:
00244 
00245     typedef std::shared_ptr<MemoryMap<typename PixelPolicy::pixel_type> > MemoryMap_shptr;
00246     typedef std::map< std::string, // filename
00247                       std::pair<MemoryMap_shptr, struct timespec> > cache_type;
00248 
00249     const std::string directory;
00250     const unsigned int tile_width_exp;
00251     const bool persistent;
00252 
00253     cache_type cache;
00254 
00255     // Used for caching the working tile.
00256     mutable MemoryMap_shptr current_tile;
00257     mutable unsigned curr_tile_num_x;
00258     mutable unsigned curr_tile_num_y;
00259 
00260 
00261   public:
00262 
00263     /**
00264      * Create a TileCache object.
00265      * @param _directory The directory where all the tiles are for a TileImage.
00266      * @param _tile_width_exp
00267      * @param _persistent
00268      */
00269 
00270     TileCache(std::string const& _directory,
00271               unsigned int _tile_width_exp,
00272               bool _persistent,
00273               unsigned int _min_cache_tiles = 4) :
00274       directory(_directory),
00275       tile_width_exp(_tile_width_exp),
00276       persistent(_persistent) {}
00277 
00278     /**
00279      * Destroy a TileCache object.
00280      */
00281 
00282     ~TileCache() {
00283       if(cache.size() > 0) {
00284         GlobalTileCache & gtc = GlobalTileCache::get_instance();
00285         gtc.release_cache_memory(this, cache.size() * get_image_size());
00286       }
00287     }
00288 
00289     void print() const {
00290       for(typename cache_type::const_iterator iter = cache.begin();
00291           iter != cache.end(); ++iter) {
00292         std::cout << "\t+ "
00293                   << directory << "/"
00294                   << (*iter).first << " "
00295                   << (*iter).second.second.tv_sec
00296                   << "/"
00297                   << (*iter).second.second.tv_nsec
00298                   << std::endl;
00299       }
00300     }
00301 
00302     /**
00303      * Get a tile. If the tile is not in the cache, the tile is loaded.
00304      *
00305      * @param x Absolut pixel coordinate.
00306      * @param y Absolut pixel coordinate.
00307      * @return Returns a shared pointer to a MemoryMap object.
00308      */
00309 
00310     std::shared_ptr<MemoryMap<typename PixelPolicy::pixel_type> >
00311     inline get_tile(unsigned int x, unsigned int y) {
00312 
00313       unsigned int tile_num_x = x >> tile_width_exp;
00314       unsigned int tile_num_y = y >> tile_width_exp;
00315 
00316       if(!(current_tile != NULL &&
00317            tile_num_x == curr_tile_num_x &&
00318            tile_num_y == curr_tile_num_y)) {
00319 
00320         // create a file name from tile number
00321         char filename[PATH_MAX];
00322         snprintf(filename, sizeof(filename), "%d_%d.dat", tile_num_x, tile_num_y);
00323         //debug(TM, "filename is: [%s]", filename);
00324 
00325         // if filename/ object is not in cache, load the tile
00326         typename cache_type::const_iterator iter = cache.find(filename);
00327 
00328         if(iter == cache.end()) {
00329           //cleanup_cache();
00330           GlobalTileCache & gtc = GlobalTileCache::get_instance();
00331           bool ok = gtc.request_cache_memory(this, get_image_size());
00332           assert(ok == true);
00333           struct timespec now;
00334           GET_CLOCK(now);
00335 
00336           cache[filename] = std::make_pair(load(filename), now);
00337 #ifdef TILECACHE_DEBUG
00338           gtc.print_table();
00339 #endif
00340         }
00341 
00342         current_tile = cache[filename].first;
00343         curr_tile_num_x = tile_num_x;
00344         curr_tile_num_y = tile_num_y;
00345 
00346       }
00347 
00348       return current_tile;
00349     }
00350 
00351   protected:
00352 
00353     /**
00354      * Remove the oldest entry from the cache.
00355      */
00356     void cleanup_cache() {
00357 
00358       if(cache.size() == 0) return;
00359 
00360       struct timespec oldest_clock_val;
00361       GET_CLOCK(oldest_clock_val);
00362 
00363       typename cache_type::iterator oldest = cache.begin();
00364 
00365       for(typename cache_type::iterator iter = cache.begin();
00366           iter != cache.end(); ++iter) {
00367 
00368         struct timespec clock_val = (*iter).second.second;
00369         if(clock_val < oldest_clock_val) {
00370           oldest_clock_val.tv_sec = clock_val.tv_sec;
00371           oldest_clock_val.tv_nsec = clock_val.tv_nsec;
00372           oldest = iter;
00373         }
00374       }
00375 
00376       assert(oldest != cache.end());
00377       (*oldest).second.first.reset(); // explicit reset of smart pointer
00378       cache.erase(oldest);
00379 #ifdef TILECACHE_DEBUG
00380       debug(TM, "local cache: %d entries after remove\n", cache.size());
00381 #endif
00382       GlobalTileCache & gtc = GlobalTileCache::get_instance();
00383       gtc.release_cache_memory(this, get_image_size());
00384 
00385     }
00386 
00387 
00388   private:
00389 
00390     /**
00391      * Get image size in bytes.
00392      */
00393     size_t get_image_size() const {
00394       return sizeof(typename PixelPolicy::pixel_type) * (1<< tile_width_exp) * (1<< tile_width_exp);
00395     }
00396 
00397     /**
00398      * Load a tile from an image file.
00399      * @param filename Just the name of the file to load. The filename is
00400      *     relative to the \p directory.
00401      */
00402     std::shared_ptr<MemoryMap<typename PixelPolicy::pixel_type> >
00403     load(std::string const& filename) const {
00404 
00405       //debug(TM, "directory: [%s] file: [%s]", directory.c_str(), filename.c_str());
00406       MemoryMap_shptr mem(new MemoryMap<typename PixelPolicy::pixel_type>
00407                           (1 << tile_width_exp,
00408                            1 << tile_width_exp,
00409                            MAP_STORAGE_TYPE_PERSISTENT_FILE,
00410                            join_pathes(directory, filename)));
00411 
00412       return mem;
00413     }
00414 
00415 
00416   }; // end of class TileCache
00417 
00418 }
00419 
00420 #endif