mabain/src/free_list.h

   1 /**
   2  * Copyright (C) 2017 Cisco Inc.
   3  *
   4  * This program is free software: you can redistribute it and/or  modify
   5  * it under the terms of the GNU General Public License, version 2,
   6  * as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15  */
  16
  17 // @author Changxue Deng <chadeng@cisco.com>
  18
  19 #ifndef __FREE_LIST_H__
  20 #define __FREE_LIST_H__
  21
  22 #include <cstdlib>
  23 #include <string>
  24
  25 #include "mb_lsq.h"
  26 #include "error.h"
  27 #include "lock_free.h"
  28
  29 #define MAX_BUFFER_PER_LIST    256
  30
  31 // Manage resource allocation/free using linked list
  32 namespace mabain {
  33
  34 typedef struct _BufferCache
  35 {
  36     size_t buf_index;
  37     size_t buf_offset;
  38 } BufferCache;
  39
  40 class FreeList
  41 {
  42 public:
  43     FreeList(const std::string &file_path, size_t buff_alignment, size_t max_n_buff,
  44              size_t max_buff_per_list = MAX_BUFFER_PER_LIST);
  45     ~FreeList();
  46
  47     // Free a buffer by adding it to the free list
  48     int AddBuffer(size_t offset, size_t size);
  49     // Reserve a buffer by removing it from the free list
  50     int RemoveBuffer(size_t &offset, size_t size);
  51     // Release alignment buffer
  52     void ReleaseAlignmentBuffer(size_t old_offset, size_t alignment_offset);
  53
  54     bool GetBufferByIndex(size_t buf_index, size_t &offset);
  55
  56     void Empty();
  57
  58     // Read buffer list from disk
  59     int LoadListFromDisk();
  60     // Save buffer list to disk
  61     int StoreListOnDisk();
  62     // Get buffer count
  63     int64_t Count() const;
  64     // Get total freed buffer size in the list
  65     size_t GetTotSize() const;
  66
  67     inline int      AddBufferByIndex(size_t buf_index, size_t offset);
  68     inline size_t   RemoveBufferByIndex(size_t buf_index);
  69     inline size_t   GetAlignmentSize(size_t size) const;
  70     inline size_t   GetBufferIndex(size_t size) const;
  71     inline uint64_t GetBufferCountByIndex(size_t buf_index) const;
  72     inline size_t   GetBufferSizeByIndex(size_t buf_index) const;
  73     inline int      ReleaseBuffer(size_t offset, size_t size);
  74
  75 private:
  76     int ReuseBuffer(size_t buf_index, size_t offset);
  77
  78     // file path where the list will be serialized and stored
  79     std::string list_path;
  80     // buffer/memory alignment
  81     size_t alignment;
  82     // maximum number of buffers
  83     size_t max_num_buffer;
  84     // maximum buffer per list
  85     // This restriction is to limit memory usage.
  86     size_t max_buffer_per_list;
  87     // number of separated buffers
  88     MBlsq **buffer_free_list;
  89     // total count of freed buffers
  90     int64_t count;
  91     // totol size allocted for all the buffers
  92     size_t tot_size;
  93 };
  94
  95 inline size_t FreeList::GetAlignmentSize(size_t size) const
  96 {
  97 #ifdef __DEBUG__
  98     assert(size > 0 && size < max_num_buffer*alignment);
  99 #endif
 100     size_t alignment_mod = size % alignment;
 101     if(alignment_mod == 0)
 102         return size;
 103     return (size + alignment - alignment_mod);
 104 }
 105
 106 inline size_t FreeList::GetBufferIndex(size_t size) const
 107 {
 108 #ifdef __DEBUG__
 109     assert(size > 0 && size < max_num_buffer*alignment);
 110 #endif
 111     return ((size - 1) / alignment);
 112 }
 113
 114 inline uint64_t FreeList::GetBufferCountByIndex(size_t buf_index) const
 115 {
 116 #ifdef __DEBUG__
 117     assert(buf_index < max_num_buffer);
 118 #endif
 119     return buffer_free_list[buf_index]->Count();
 120 }
 121
 122 inline size_t FreeList::GetBufferSizeByIndex(size_t buf_index) const
 123 {
 124 #ifdef __DEBUG__
 125     assert(buf_index < max_num_buffer);
 126 #endif
 127     return (buf_index + 1) * alignment;
 128 }
 129
 130 inline int FreeList::AddBufferByIndex(size_t buf_index, size_t offset)
 131 {
 132 #ifdef __DEBUG__
 133     assert(buf_index < max_num_buffer);
 134 #endif
 135
 136     if(buffer_free_list[buf_index]->Count() > (unsigned)max_buffer_per_list)
 137     {
 138         ReuseBuffer(buf_index, offset);
 139         return MBError::SUCCESS;
 140     }
 141
 142     count++;
 143     tot_size += (buf_index + 1) * alignment;
 144     return buffer_free_list[buf_index]->AddIntToTail(offset);
 145 }
 146
 147 inline size_t FreeList::RemoveBufferByIndex(size_t buf_index)
 148 {
 149 #ifdef __DEBUG__
 150     assert(buf_index < max_num_buffer);
 151 #endif
 152     count--;
 153     tot_size -= (buf_index + 1) * alignment;
 154     return buffer_free_list[buf_index]->RemoveIntFromHead();
 155 }
 156
 157 inline int FreeList::ReleaseBuffer(size_t offset, size_t size)
 158 {
 159 #ifdef __DEBUG__
 160     assert(size > 0 && size < max_num_buffer*alignment);
 161 #endif
 162     size_t buf_index = GetBufferIndex(size);
 163     return AddBufferByIndex(buf_index, offset);
 164 }
 165
 166 }
 167
 168 #endif