AllocationHelpers.H

Go to the documentation of this file.

/*! @file
    @author Shane Grant
    @copyright GNU Public License (GPL v3)
    @section License
    @verbatim
    // ////////////////////////////////////////////////////////////////////////
    //              The iLab Neuromorphic Robotics Toolkit (NRT)             //
    // Copyright 2010-2012 by the University of Southern California (USC)    //
    //                          and the iLab at USC.                         //
    //                                                                       //
    //                iLab - University of Southern California               //
    //                Hedco Neurociences Building, Room HNB-10               //
    //                    Los Angeles, Ca 90089-2520 - USA                   //
    //                                                                       //
    //      See http://ilab.usc.edu for information about this project.      //
    // ////////////////////////////////////////////////////////////////////////
    // This file is part of The iLab Neuromorphic Robotics Toolkit.          //
    //                                                                       //
    // The iLab Neuromorphic Robotics Toolkit is free software: you can      //
    // redistribute it and/or modify it under the terms of the GNU General   //
    // Public License as published by the Free Software Foundation, either   //
    // version 3 of the License, or (at your option) any later version.      //
    //                                                                       //
    // The iLab Neuromorphic Robotics Toolkit is distributed in the hope     //
    // that it will be useful, but WITHOUT ANY WARRANTY; without even the    //
    // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR       //
    // PURPOSE.  See the GNU General Public License for more details.        //
    //                                                                       //
    // You should have received a copy of the GNU General Public License     //
    // along with The iLab Neuromorphic Robotics Toolkit.  If not, see       //
    // <http://www.gnu.org/licenses/>.                                       //
    // ////////////////////////////////////////////////////////////////////////
    @endverbatim */

#ifndef INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_
#define INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_

#include <map>
#include <nrt/Core/Util/StringUtil.H>
#include <nrt/Core/Debugging/Log.H>
#include <nrt/Core/Memory/details/freelist.h>
#include <cstdlib>
#include <functional>

namespace nrt
{
  namespace memorydetail
  {
    //! Trivial allocator that just calls operator new() and operator delete()
    struct trivial_alloc
    {
      void set_debug(bool /*do_debug*/)
      {
        // no debug settings for this allocator type
      }

      void set_allow_caching(bool /*on*/)
      {
        // no caching here in any case
      }

      void show_stats(int /*verbosity*/, const char* /*pfx*/,
          const size_t block_size, const size_t overhead) const
      {
        // nothing to do here
      }

      void* allocate(size_t nbytes, nrt::rutz::free_list_base** source = 0)
      {
        if (source != 0)
          *source = 0;
        return ::operator new(nbytes);
      }

      void deallocate(void* space, nrt::rutz::free_list_base* source = 0)
      {
        assert(source == 0);
        ::operator delete(space);
      }

      void release_free_mem()
      {
        // nothing to do here
      }
    };

    //! Caching allocator with free lists for common allocation sizes
    template <size_t cache_size>
      struct fastcache_alloc
      {
        nrt::rutz::free_list_base* cache[cache_size];
        mutable size_t num_alloc[cache_size];
        bool allow_caching;

        fastcache_alloc()
          : allow_caching(true)
        {
          for (size_t i = 0; i < cache_size; ++i)
          {
            this->cache[i] = 0;
            this->num_alloc[i] = 0;
          }
        }

        fastcache_alloc(fastcache_alloc const & other) = delete;

        ~fastcache_alloc()
        {
          release_free_mem();
          for(size_t i=0; i<cache_size; ++i)
            delete cache[i];
        }

        void set_debug(bool /*do_debug*/)
        {
          // no debug settings for this allocator type
        }

        void set_allow_caching(bool on)
        {
          if (!on && this->allow_caching)
          {
            // if we are currently caching but are being asked to turn
            // off caching, then let's first free any existing caches

            this->release_free_mem();
          }
          this->allow_caching = on;
        }

        void show_stats(int verbosity, const char* pfx,
            const size_t block_size, const size_t overhead) const
        {
          size_t nused = 0;
          size_t bytes_allocated = 0;

          std::map<size_t, std::string> msgs;

          for (size_t i = 0; i < cache_size; ++i)
            if (this->cache[i] != 0)
            {
              ++nused;
              const size_t nb = (this->cache[i]->num_allocations()
                  * this->cache[i]->alloc_size());

              const size_t extra = (this->cache[i]->num_allocations()
                  - this->num_alloc[i]);

              this->num_alloc[i] = this->cache[i]->num_allocations();

              bytes_allocated += nb;

              if (verbosity <= 0)
                continue;

              std::string msg =
                nrt::sformat("%s%sfastcache[%zu/%zu]: "
                    "%10.4fMB in %zu allocations of %10.4fkB",
                    pfx ? pfx : "", pfx ? ": " : "",
                    i, cache_size, nb / (1024.0*1024.0),
                    this->cache[i]->num_allocations(),
                    this->cache[i]->alloc_size() / 1024.0);

              if (block_size > 0)
              {
                if (this->cache[i]->alloc_size() - overhead >= block_size
                    || this->cache[i]->alloc_size() - overhead <= 1)
                  msg += nrt::sformat(" (%.2fkB * %7.1f + %zuB)",
                      block_size / 1024.0,
                      (double(this->cache[i]->alloc_size() - overhead)
                       / double(block_size)),
                      overhead);
                else
                  msg += nrt::sformat(" (%.2fkB / %7.1f + %zuB)",
                      block_size / 1024.0,
                      (double(block_size)
                       / double(this->cache[i]->alloc_size() - overhead)),
                      overhead);
              }

              if (extra > 0)
                msg += nrt::sformat(" (+%zu new)", extra);

              msgs[this->cache[i]->alloc_size()] = msg;
            }

          for (std::map<size_t, std::string>::const_iterator
              itr = msgs.begin(), stop = msgs.end();
              itr != stop; ++itr)
            NRT_INFO((*itr).second.c_str());


          std::string msg =
            nrt::sformat("%s%sfastcache_alloc<%zu>: %zu/%zu cache table "
                "entries in use, %fMB total allocated",
                pfx ? pfx : "", pfx ? ": " : "",
                cache_size, nused, cache_size,
                bytes_allocated / (1024.0*1024.0));

          if (block_size > 0)
            msg += nrt::sformat(" (%.2fkB * %7.1f)",
                block_size / 1024.0,
                double(bytes_allocated) / double(block_size));

          NRT_INFO(msg.c_str());
        }

        // allocate memory block of size nbytes; also return the address
        // of the nrt::rutz::free_list_base, if any, that was used for
        // allocation
        void* allocate(size_t nbytes, nrt::rutz::free_list_base** source)
        {
          if (this->allow_caching && source != 0)
            for (size_t i = 0; i < cache_size; ++i)
            {
              if (this->cache[i] != 0)
              {
                // we found a filled slot, let's see if it matches our
                // requested size
                if (this->cache[i]->alloc_size() == nbytes)
                {
                  *source = this->cache[i];
                  return this->cache[i]->allocate(nbytes);
                }
                // else, continue
              }
              else // this->cache[i] == 0
              {
                // we found an empty slot, let's set up a new free
                // list for our requested size:
                this->cache[i] = new nrt::rutz::free_list_base(nbytes);
                *source = this->cache[i];
                return this->cache[i]->allocate(nbytes);
              }
            }

          *source = 0;
          return ::operator new(nbytes);
        }

        // deallocate memory from the given nrt::rutz::free_list_base,
        // otherwise free it globally
        void deallocate(void* space, nrt::rutz::free_list_base* source)
        {
          if (source != 0)
          {
            source->deallocate(space);
            if (!this->allow_caching)
              source->release_free_nodes();
          }
          else
          {
            ::operator delete(space);
          }
        }

        void release_free_mem()
        {
          for (size_t i = 0; i < cache_size; ++i)
            if (this->cache[i] != 0)
              this->cache[i]->release_free_nodes();
        }
      };

    //! Auxiliary information about an aligned memory allocation
    template <size_t N>
      struct alloc_info
      {
        struct data_s
        {
          // address of ALLOCATED memory, not the address returned to
          // the user:
          void* alloc_addr;

          // the freelist from which this memory was allocated, or else
          // null:
          nrt::rutz::free_list_base* source;

          unsigned long align() const
          {
            return reinterpret_cast<unsigned long>(this->alloc_addr) % N;
          }

          unsigned long adjust() const
          {
            return N-this->align();
          }

          void* user_addr() const
          {
            return
              static_cast<char*>(this->alloc_addr)
              +this->adjust()
              +N;
          }

          unsigned long user_align() const
          {
            return reinterpret_cast<unsigned long>(this->user_addr()) % N;
          }

          void print() const
          {
            NRT_INFO(nrt::sformat("alloc: internal=[%p (align%zu=%lu)], "
                  "user=[%p (align%zu=%lu)]",
                  this->alloc_addr, N, this->align(), this->user_addr(), N, this->user_align()));
          }

        };
        data_s data;
        static const int pad_size = int(N) - int(sizeof(data_s));
        static_assert(pad_size >= 0, "Minimum alignment size is 16 bytes");
        char pad[pad_size];
      };

    //! Allocate memory that is aligned on an N-byte boundary
    template <class src_type, size_t N>
      struct aligned_alloc
      {
        src_type src_alloc;

        bool do_debug_printing;
        double nbytes_allocated;
        size_t nallocations;
        size_t nbytes_current;
        size_t nallocations_current;

        struct assertions
        {
          static_assert(sizeof(alloc_info<N>) == N, "Sizeof assumptions about alloc_info are wrong!");
        };

        aligned_alloc()
          :
            do_debug_printing(false),
            nbytes_allocated(0.0),
            nallocations(0),
            nbytes_current(0),
            nallocations_current(0)
        {}

        aligned_alloc(aligned_alloc const & other) = delete;

        void set_debug(bool do_debug)
        {
          this->do_debug_printing = do_debug;

          // also call set_debug() on our child object
          src_alloc.set_debug(do_debug);
        }

        void set_allow_caching(bool on)
        {
          src_alloc.set_allow_caching(on);
        }

        void show_stats(int verbosity, const char* pfx,
            const size_t block_size, const size_t overhead) const
        {
          NRT_INFO(nrt::sformat("%s%saligned_alloc<%zu>: "
                "all-time: [%fMB in %zu allocations], "
                "current: [%fMB in %zu allocations]",
                pfx ? pfx : "",
                pfx ? ": " : "",
                N,
                double(this->nbytes_allocated)/(1024.0*1024.0), this->nallocations,
                double(this->nbytes_current)/(1024.0*1024.0), this->nallocations_current));

          // also show stats for our child object
          src_alloc.show_stats(verbosity, pfx, block_size, overhead+2*N);
        }

        void* allocate(size_t user_nbytes)
        {
          alloc_info<N> info;
          info.data.source = 0;

          // We request extra space beyond what the user wants -- N extra
          // bytes allow us to return an address to the user that is
          // aligned to a N-byte boundary, and sizeof(alloc_info<N>) extra
          // bytes allow us to stick some auxiliary info just ahead of the
          // address that we return to the user. Note that for convenience
          // we have set things up so that sizeof(alloc_info<N>)==N, so
          // the number of extra bytes that we need is just 2*N.
          size_t alloc_nbytes = user_nbytes+2*N;

          info.data.alloc_addr =
            this->src_alloc.allocate(alloc_nbytes, &info.data.source);

          /* We will set things up like this:

             +- address = return value of src_alloc.allocate()
             |
             |                                      +- address = return value
             |                                      |     of this function
             v                                      v

             +------------------+-------------------+------------------------+
             | len==adjust      | len==N            | len==user_nbytes       |
             | contents:        | contents:         | contents:              |
             |   unused         |   alloc_info<N>   |   empty space for user |
             | alignment:       | alignment:        | alignment:             |
             |   unknown        |   N-byte boundary |   N-byte boundary      |
             +------------------+-------------------+------------------------+

*/

          void* const user_addr = info.data.user_addr();

          static_cast<alloc_info<N>*>(user_addr)[-1].data = info.data;

          //this->nbytes_allocated += info.data.alloc_nbytes;
          ++this->nallocations;
          //this->nbytes_current += info.data.alloc_nbytes;
          ++this->nallocations_current;

          if (this->do_debug_printing)
          {
            info.data.print();
            this->show_stats(0, 0, 0, 0);
          }

          return user_addr;
        }

        void deallocate(void* user_addr)
        {
          const alloc_info<N>* const info =
            static_cast<alloc_info<N>*>(user_addr) - 1;

          //this->nbytes_current -= info->data.alloc_nbytes;
          --this->nallocations_current;

          if (this->do_debug_printing)
          {
            info->data.print();
            this->show_stats(0, 0, 0, 0);
          }

          this->src_alloc.deallocate(info->data.alloc_addr, info->data.source);
        }

        void release_free_mem()
        {
          this->src_alloc.release_free_mem();
        }
      };
  } // namespace memorydetail
} // namespace nrt

#endif // INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_