src/storage/TreeIndex.cxx

   1 /***************************************************************************
   2  *   Copyright (C) 2007 by www.databasecache.com                           *
   3  *   Contact: praba_tuty@databasecache.com                                 *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15   ***************************************************************************/
  16 #include<Index.h>
  17 #include<CatalogTables.h>
  18 #include<Lock.h>
  19 #include<Debug.h>
  20 #include<Table.h>
  21 #include<TableImpl.h>
  22 #include<Predicate.h>
  23 #include<PredicateImpl.h>
  24 DbRetVal TreeIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
  25 {
  26     DbRetVal rv = OK;
  27     TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
  28     Database *db = new Database();
  29     db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
  30     db->setProcSlot(sysdb->procSlot);
  31     CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;
  32     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
  33     //HashIndexInfo populated here
  34     HashIndexInfo *info = new HashIndexInfo();
  35     info->indexPtr = (char *)iptr;
  36     info->noOfBuckets = iptr->noOfBuckets_;
  37     info->isUnique = iptr->isUnique_;
  38     info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
  39     info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
  40     info->indType = iptr->indexType_;
  41     TreeIndex *treeInd = (TreeIndex*)Index::getIndex(iptr->indexType_);
  42     int pos=0;
  43     TreeNode *fltnode = start->locateNode(db, start, tUndoInfo->tuple_, info,rv);
  44     if (NULL == fltnode){
  45         delete db;
  46         delete info;
  47         return rv;
  48     } //First Level Node Not found
  49     TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, info, tUndoInfo->tuple_, &pos);
  50     if (NULL == iter){
  51         fltnode->mutex_.releaseShareLock(db->procSlot);
  52         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
  53         delete db;
  54         delete info;
  55         return OK;
  56     } //element not found
  57     rv = treeInd->removeElement(db, iter, tUndoInfo->tuple_, info);
  58     if( rv != OK ){
  59         fltnode->mutex_.releaseShareLock(db->procSlot);
  60         printError(rv, "Romove from TreeNode Failed ");
  61         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
  62         delete db;
  63         delete info;
  64         return rv;
  65     }
  66     if(0 == iter->noElements_)
  67     {
  68         treeInd->removeNode(db, tUndoInfo->cIndex_, fltnode,iter, pos);
  69     }else { fltnode->mutex_.releaseShareLock(db->procSlot);
  70         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
  71     }
  72     delete db;
  73     delete info;
  74     return rv;
  75 }
  76
  77 DbRetVal TreeIndex::insertLogicalUndoLog(Database *sysdb, void *data)
  78 {
  79     DbRetVal rc = OK;
  80     TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
  81     Database *db = new Database();
  82     db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
  83     db->setProcSlot(sysdb->procSlot);
  84     CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;//CINDEX
  85     //HashIndexInfo populated here
  86     HashIndexInfo *info = new HashIndexInfo();
  87     info->indexPtr = (char *)iptr;
  88     info->noOfBuckets = iptr->noOfBuckets_;
  89     info->isUnique = iptr->isUnique_;
  90     info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
  91     info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
  92     info->indType = iptr->indexType_;
  93     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
  94     int offset = info->fldOffset;
  95     DataType type = info->type;
  96     void *keyPtr =(void*)((char*)tUndoInfo->tuple_ + offset);
  97     if (start == NULL)
  98     {
  99         //Currently Nodes are not deleted
 100         printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
 101         Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 102         TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 103         if (tnode == NULL)
 104         {
 105             printError(rc, "Exit TreeNode::Insert - 1 tnode=NULL");
 106             delete info;
 107             return rc;
 108         }
 109         tnode->mutex_.init("TNODE-R");
 110         tnode->min_ = tUndoInfo->tuple_;
 111         tnode->max_ = tUndoInfo->tuple_;
 112         tnode->noElements_ =1;
 113         tnode->next_ = NULL;
 114         tnode->prev_ = NULL;
 115         tnode->balance_ = 0;
 116         char **rec = (char**)((char*) tnode + sizeof(TreeNode));
 117         //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
 118         *rec = (char*) tUndoInfo->tuple_;
 119
 120         printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
 121         Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
 122         TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rc);
 123         if (NULL == ftnode)
 124         {
 125             printError(rc, "Unable to allocate tree node");
 126             chunk->free(db, tnode);
 127             delete info;
 128             return rc;
 129         }
 130         ftnode->mutex_.init("TNODE-I");
 131         ftnode->min_= NULL;
 132         ftnode->max_ = NULL;
 133         ftnode->noElements_ =1;
 134         ftnode->next_ = NULL;
 135         ftnode->prev_ = NULL;
 136         ftnode->balance_ = 0;
 137         char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
 138         *tn = (char*)tnode;
 139         //iptr->hashNodeChunk_ = ftnode;
 140         if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
 141         {
 142             printError(ErrLockTimeOut, "Lock timeout..retry");
 143             chunk->free(db, tnode);
 144             chunk->free(db, ftnode);
 145             delete info;
 146             return ErrLockTimeOut;
 147         }
 148     }else {
 149         rc = start->insert(db, info, iptr, tUndoInfo->tuple_);
 150         if (rc != OK){
 151             delete db; delete info;
 152             printError(rc, "Error in tree node insertion\n");
 153             return rc;
 154         }
 155     }
 156     delete db;
 157     delete info;
 158     return rc;
 159
 160 }
 161
 162 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 163 {
 164     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 165     CINDEX *iptr = (CINDEX*)indexPtr;
 166     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
 167     DbRetVal rc = OK;
 168     int offset = info->fldOffset;
 169     DataType type = info->type;
 170     void *keyPtr =(void*)((char*)tuple + offset);
 171     //TreeUndoLogInfo Populated here
 172     TreeUndoLogInfo hInfo;
 173     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 174     hInfo.tuple_ = tuple;
 175     hInfo.cIndex_= indexPtr;
 176     if (start == NULL)
 177     {
 178         printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
 179         Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 180         TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
 181         if (tnode == NULL)
 182         {
 183             printError(rc, "Unable to allocate tree node");
 184             return rc;
 185         }
 186         tnode->mutex_.init("TNODE-R");
 187         tnode->min_ = tuple;
 188         tnode->max_ = tuple;
 189         tnode->noElements_ =1;
 190         tnode->next_ = NULL;
 191         tnode->prev_ = NULL;
 192         tnode->balance_ = 0;
 193         char **rec = (char**)((char*) tnode + sizeof(TreeNode));
 194         //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
 195         *rec = (char*) tuple;
 196
 197         printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
 198         TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
 199         if (NULL == ftnode)
 200         {
 201             printError(rc, "Unable to allocate tree node");
 202             chunk->free(tbl->db_, tnode);
 203             return rc;
 204         }
 205         ftnode->mutex_.init("TNODE-I");
 206         ftnode->min_= NULL;
 207         ftnode->max_ = NULL;
 208         ftnode->noElements_ =1;
 209         ftnode->next_ = NULL;
 210         ftnode->prev_ = NULL;
 211         ftnode->balance_ = 0;
 212         //TODO: Handle when two process try to allocate first node
 213         char **tn=(char**)((char*) ftnode + sizeof(TreeNode));
 214         *tn = (char*)tnode;
 215         if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
 216         {
 217             printError(ErrLockTimeOut, "Lock timeout..retry");
 218             chunk->free(tbl->db_, tnode);
 219             chunk->free(tbl->db_, ftnode);
 220             return ErrLockTimeOut;
 221         }
 222
 223     }else {
 224         rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
 225         if (rc != OK){
 226             printError(rc, "Error in tree node insertion for tuple %x", tuple);
 227             return rc;
 228         }
 229     }
 230     //start->displayAll(offset);
 231     if(!undoFlag){
 232         rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
 233         if (rc !=OK)
 234         {
 235              //Reverse back
 236              int pos=0;
 237              start = (TreeNode*) iptr->hashNodeChunk_;
 238              TreeNode *fltnode = start->locateNode(tbl->sysDB_,start, tuple, indInfo,rc);
 239              if (NULL == fltnode)
 240              {
 241                   return rc;
 242              } //First Level Node Not found
 243              TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
 244              if (NULL == iter){
 245                 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
 246                 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 247                 return OK;
 248              } //element not found
 249              rc = removeElement(tbl->getDB(), iter, tuple, info);
 250              if( rc != OK )
 251              {
 252                  fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
 253                  printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 254                  printError(rc, "Romove from TreeNode Failed ");
 255                  return rc;
 256              }
 257              if(0 == iter->noElements_)
 258              {
 259                  removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
 260              }else
 261              {
 262                  fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
 263                  printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 264              }
 265
 266              printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
 267              return rc;
 268
 269         }
 270     }
 271     return rc;
 272 }
 273
 274
 275 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 276 {
 277     DbRetVal rc = OK;
 278     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 279     CINDEX *iptr = (CINDEX*)indexPtr;
 280     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
 281     int pos=0;
 282     TreeNode *fltnode = start->locateNode(tbl->getDB(),start, tuple, indInfo,rc);
 283     if (NULL == fltnode) return rc; //First Level Node Not found
 284     TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
 285     if (NULL == iter) {
 286         //element not found
 287         fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
 288         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 289         return OK;
 290      }
 291     rc = removeElement(tbl->getDB(), iter, tuple, info);
 292     if( rc != OK ){
 293         fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
 294         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 295         printError(rc, "Remove from TreeNode Failed");
 296         return rc;
 297     }
 298     if(0 == iter->noElements_)
 299     {
 300         removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
 301     }else
 302     {
 303         fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
 304         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 305     }
 306     TreeUndoLogInfo hInfo;
 307     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 308     hInfo.tuple_ = tuple;
 309     hInfo.cIndex_= indexPtr;
 310     if (!undoFlag) {
 311         rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
 312         if( rc != OK){
 313             //Reverse back
 314             //Currently nodes are not freed
 315             rc = start->insert(tbl->db_, info, iptr, tuple);
 316             if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
 317             printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
 318             return rc;
 319         }
 320    }
 321    return rc;
 322 }
 323
 324 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
 325 {
 326     CINDEX *iptr = (CINDEX*)indexPtr;
 327     char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
 328     char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
 329     memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
 330     memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
 331     free(tmp);
 332     fltnode->noElements_--;
 333     if(node->prev_!=NULL) node->prev_->next_= node->next_;
 334     if(node->next_!=NULL) node->next_->prev_= node->prev_;
 335     Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 336     chunk->free(db, node);
 337     printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
 338     if(fltnode->noElements_== 0)
 339     {
 340         if(fltnode->prev_!=NULL) {
 341             fltnode->prev_->next_= fltnode->next_;
 342         }
 343         else {
 344             iptr->hashNodeChunk_ = fltnode->next_ ;
 345         }
 346         if(fltnode->next_!=NULL) {
 347             fltnode->next_->prev_= fltnode->prev_;
 348         }
 349         //need discussion in the above situation to solve concureny
 350         printDebug(DM_TreeIndex,"TreeNode from first level Freed");
 351         fltnode->mutex_.releaseShareLock(db->procSlot);
 352         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 353         chunk->free(db, fltnode);
 354     }else{
 355         fltnode->mutex_.releaseShareLock(db->procSlot);
 356         printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
 357     }
 358 }
 359
 360 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
 361 {
 362     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 363     int loc=0, middle=0, start=0, end=iter->noElements_-1;
 364     char **rec = (char**)((char*)iter + sizeof(TreeNode));
 365     DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
 366     if (OK != ret) {
 367          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 368          return ErrLockTimeOut;
 369     }
 370     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 371     {
 372         loc = middle;
 373         char *record = ((char*)*(rec+middle)) + info->fldOffset;
 374         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
 375                                            info->type, info->compLength);
 376         if(res)
 377         {
 378             end = middle - 1;
 379         }
 380         else
 381         {
 382             res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
 383                                           info->type, info->compLength);
 384             if (res) {
 385                 start = middle + 1;
 386                 loc = start;
 387             } else {
 388                 loc = middle;
 389                 break;
 390             }
 391         }
 392     }
 393     if (loc == iter->noElements_-1)
 394     {
 395         iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
 396     }else {
 397        char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 398        memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
 399                                     sizeof(void *) * (iter->noElements_ - loc));
 400        memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
 401                                     sizeof(void *) * (iter->noElements_ - loc));
 402        free(tmp);
 403     }
 404     if(loc==0)
 405     {
 406        iter->min_ = *(char**)rec ;
 407     }
 408     iter->noElements_--;
 409     iter->mutex_.releaseShareLock(db->procSlot);
 410     return OK;
 411 }
 412
 413
 414 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 415 {
 416     CINDEX *iptr = (CINDEX*)indexPtr;
 417
 418     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 419     //check whether the index key is updated or not
 420     //if it is not updated return from here
 421     bool keyNotUpdated = false;
 422     FieldIterator idxFldIter = info->idxFldList.getIterator();
 423     while (idxFldIter.hasElement())
 424     {
 425         FieldDef *idef = idxFldIter.nextElement();
 426         FieldIterator fldIter = tbl->fldList_.getIterator();
 427         while (fldIter.hasElement())
 428         {
 429             FieldDef *def = fldIter.nextElement();
 430             if (0 == strcmp(def->fldName_, idef->fldName_))
 431             {
 432                 if (NULL != def->bindVal_)
 433                 {
 434                     //Not Implemented
 435                     return ErrNotYet;
 436                 }
 437                keyNotUpdated = true;
 438                break;
 439             }
 440         }
 441     }
 442     if (keyNotUpdated)
 443     {
 444         return OK;
 445     }
 446     return ErrNotYet;
 447 }
 448
 449 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
 450 {
 451     struct timeval timeout, timeval;
 452     timeout.tv_sec = Conf::config.getMutexSecs();
 453     timeout.tv_usec = Conf::config.getMutexUSecs();
 454     int tries=0;
 455     int totalTries = Conf::config.getMutexRetries() *2;
 456     int ret =0;
 457     while (tries < totalTries)
 458     {
 459         ret = 0;
 460         if (isX)
 461            ret = node->mutex_.getExclusiveLock(procSlot,true);
 462         else
 463            ret = node->mutex_.getShareLock(procSlot,true);
 464         if (ret == 0) break;
 465         timeval.tv_sec = timeout.tv_sec;
 466         timeval.tv_usec = timeout.tv_usec;
 467         os::select(0, 0, 0, 0, &timeval);
 468         tries++;
 469     }
 470     if (tries >= totalTries) return ErrLockTimeOut;
 471     return OK;
 472
 473 }
 474
 475 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
 476 {
 477     struct timeval timeout, timeval;
 478     timeout.tv_sec = Conf::config.getMutexSecs();
 479     timeout.tv_usec = Conf::config.getMutexUSecs();
 480     int tries=0;
 481     int totalTries = Conf::config.getMutexRetries() *2;
 482     int ret =0;
 483     while (tries < totalTries)
 484     {
 485         ret = 0;
 486         ret = node->mutex_.getExclusiveLock(procSlot,true, true);
 487         if (ret == 0) break;
 488         timeval.tv_sec = timeout.tv_sec;
 489         timeval.tv_usec = timeout.tv_usec;
 490         os::select(0, 0, 0, 0, &timeval);
 491         tries++;
 492     }
 493     if (tries >= totalTries) return ErrLockTimeOut;
 494     return OK;
 495 }
 496