mabain/src/dict_mem.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 __DICTMEM_H__
  20 #define __DICTMEM_H__
  21
  22 #include <string>
  23 #include <memory>
  24 #include <stdint.h>
  25 #include <string.h>
  26 #include <pthread.h>
  27 #include <assert.h>
  28
  29 #include "drm_base.h"
  30 #include "db.h"
  31 #include "mabain_consts.h"
  32 #include "mb_data.h"
  33 #include "rollable_file.h"
  34 #include "mb_lsq.h"
  35 #include "free_list.h"
  36 #include "lock_free.h"
  37 #include "error.h"
  38
  39 namespace mabain {
  40
  41 typedef struct _NodePtrs
  42 {
  43     size_t   offset;
  44     uint8_t *ptr;
  45
  46     uint8_t *edge_key_ptr;
  47     uint8_t *edge_ptr;
  48 } NodePtrs;
  49
  50 // Memory management class for the dictionary
  51 class DictMem : public DRMBase
  52 {
  53 public:
  54     DictMem(const std::string &mbdir, bool init_header, size_t memsize,
  55             int mode, uint32_t block_size, int max_num_blk, uint32_t queue_size);
  56     void Destroy();
  57     virtual ~DictMem();
  58
  59     bool IsValid() const;
  60     void PrintStats(std::ostream &out_stream) const;
  61
  62     void InitNodePtrs(uint8_t *ptr, int nt, NodePtrs &node_ptrs);
  63     void InitEdgePtrs(const NodePtrs &node_ptrs, int index,
  64                   EdgePtrs &edge_ptrs);
  65     void AddRootEdge(EdgePtrs &edge_ptrs, const uint8_t *key, int len,
  66                   size_t data_offset);
  67     int  InsertNode(EdgePtrs &edge_ptrs, int match_len, size_t data_offset,
  68                   MBData &data);
  69     int  AddLink(EdgePtrs &edge_ptrs, int match_len, const uint8_t *key,
  70                   int key_len, size_t data_off, MBData &data);
  71     int  UpdateNode(EdgePtrs &edge_ptrs, const uint8_t *key, int key_len,
  72                   size_t data_off);
  73     bool FindNext(const unsigned char *key, int keylen, int &match_len,
  74                   EdgePtrs &edge_ptr, uint8_t *key_tmp) const;
  75     int  GetRootEdge(size_t rc_off, int nt, EdgePtrs &edge_ptrs) const;
  76     int  GetRootEdge_Writer(bool rc_mode, int nt, EdgePtrs &edge_ptrs) const;
  77     int  ClearRootEdge(int nt) const;
  78     void ReserveData(const uint8_t* key, int size, size_t &offset,
  79                      bool map_new_sliding=true);
  80     int  NextEdge(const uint8_t *key, EdgePtrs &edge_ptrs,
  81                   uint8_t *tmp_buff, MBData &mbdata) const;
  82     int  RemoveEdgeByIndex(const EdgePtrs &edge_ptrs, MBData &data);
  83     void InitRootNode();
  84     inline void WriteEdge(const EdgePtrs &edge_ptrs) const;
  85     void WriteData(const uint8_t *buff, unsigned len, size_t offset) const;
  86     inline size_t GetRootOffset() const;
  87     void ClearMem() const;
  88     const int* GetNodeSizePtr() const;
  89     void ResetSlidingWindow() const;
  90
  91     void InitLockFreePtr(LockFree *lf);
  92
  93     void Flush() const;
  94
  95     // Updates in RC mode
  96     size_t InitRootNode_RC();
  97     int    ClearRootEdges_RC() const;
  98
  99     // empty edge, used for clearing edges
 100     static const uint8_t empty_edge[EDGE_SIZE];
 101
 102 private:
 103     bool     ReserveNode(int nt, size_t &offset, uint8_t* &ptr);
 104     void     ReleaseNode(size_t offset, int nt);
 105     void     ReleaseBuffer(size_t offset, int size);
 106     void     UpdateTailEdge(EdgePtrs &edge_ptrs, int match_len, MBData &data,
 107                             EdgePtrs &tail_edge, uint8_t &new_key_first,
 108                             bool &map_new_sliding);
 109     void     UpdateHeadEdge(EdgePtrs &edge_ptrs, int match_len,
 110                             MBData &data, int &release_buffer_size,
 111                             size_t &edge_str_off, bool &map_new_sliding);
 112     void     RemoveRootEdge(const EdgePtrs &edge_ptrs);
 113     int      RemoveEdgeSizeN(const EdgePtrs &edge_ptrs, int nt, size_t node_offset,
 114                             uint8_t *old_node_buffer, size_t &str_off_rel,
 115                             int &str_size_rel, size_t parent_edge_offset);
 116     int      RemoveEdgeSizeOne(uint8_t *old_node_buffer, size_t parent_edge_offset,
 117                             size_t node_offset, int nt, size_t &str_off_rel,
 118                             int &str_size_rel);
 119
 120     int *node_size;
 121     bool is_valid;
 122
 123     size_t root_offset;
 124     uint8_t *node_ptr;
 125
 126     // lock free pointer
 127     LockFree *lfree;
 128
 129     // header file
 130     std::shared_ptr<MmapFileIO> header_file;
 131
 132     size_t root_offset_rc;
 133 };
 134
 135 inline void DictMem::WriteEdge(const EdgePtrs &edge_ptrs) const
 136 {
 137     if(edge_ptrs.offset + EDGE_SIZE > header->m_index_offset)
 138     {
 139         std::cerr << "invalid edge write: " << edge_ptrs.offset << " " << EDGE_SIZE
 140                   << " " << header->m_index_offset << "\n";
 141         throw (int) MBError::OUT_OF_BOUND;
 142     }
 143
 144     if(kv_file->RandomWrite(edge_ptrs.ptr, EDGE_SIZE, edge_ptrs.offset) != EDGE_SIZE)
 145         throw (int) MBError::WRITE_ERROR;
 146 }
 147
 148 inline size_t DictMem::GetRootOffset() const
 149 {
 150     return root_offset;
 151 }
 152
 153 // update the edge pointers for fast access
 154 // node_ptrs.offset and node_ptrs.ptr[1] must already be populated before calling this function
 155 inline void DictMem::InitEdgePtrs(const NodePtrs &node_ptrs, int index, EdgePtrs &edge_ptrs)
 156 {
 157     int edge_off = NODE_EDGE_KEY_FIRST + node_ptrs.ptr[1] + 1  + index*EDGE_SIZE;
 158     edge_ptrs.offset = node_ptrs.offset + edge_off;
 159     edge_ptrs.ptr = node_ptrs.ptr + edge_off;
 160     edge_ptrs.len_ptr = edge_ptrs.ptr + EDGE_LEN_POS;
 161     edge_ptrs.flag_ptr = edge_ptrs.ptr + EDGE_FLAG_POS;
 162     edge_ptrs.offset_ptr = edge_ptrs.flag_ptr + 1;
 163 }
 164
 165 inline void InitTempEdgePtrs(EdgePtrs &edge_ptrs)
 166 {
 167     edge_ptrs.ptr = edge_ptrs.edge_buff;
 168     edge_ptrs.len_ptr = edge_ptrs.ptr + EDGE_LEN_POS;
 169     edge_ptrs.flag_ptr = edge_ptrs.ptr + EDGE_FLAG_POS;
 170     edge_ptrs.offset_ptr = edge_ptrs.flag_ptr + 1;
 171 }
 172
 173 // node_ptrs.offset must be populated before caling this function
 174 inline void DictMem::InitNodePtrs(uint8_t *ptr, int nt, NodePtrs &node_ptrs)
 175 {
 176     node_ptrs.ptr = ptr;
 177     nt++;
 178     node_ptrs.edge_key_ptr = ptr + NODE_EDGE_KEY_FIRST;
 179     node_ptrs.edge_ptr = node_ptrs.edge_key_ptr + nt;
 180 }
 181
 182 }
 183
 184 #endif