1 /***************************************************************************
2 * Copyright (C) 2007 by www.databasecache.com *
3 * Contact: praba_tuty@databasecache.com *
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. *
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. *
15 ***************************************************************************/
21 #include<CatalogTables.h>
23 // sets the size of the Chunk allocator for fixed size
25 // we need one integer to store book keeping information
26 // whether the storage allocation unit is used of not
27 // when it is deleted this flag is only set to unused
28 void Chunk::setSize(size_t size
)
31 size_t needSize
= size
+ sizeof(int);
32 size_t multiple
= (size_t) os::floor(needSize
/ sizeof(size_t));
33 size_t rem
= needSize
% sizeof(size_t);
35 allocSize_
= needSize
;
37 allocSize_
= (multiple
+ 1) * sizeof(size_t);
40 void* Chunk::allocateForLargeDataSize(Database
*db
)
42 PageInfo
* pageInfo
= ((PageInfo
*)curPage_
);
43 DbRetVal ret
= db
->getAllocDatabaseMutex();
46 printError(ErrLockTimeOut
,"Unable to acquire alloc database Mutex");
50 //check whether we have space in curPage
51 if (pageInfo
->hasFreeSpace_
== 1)
53 char *data
= ((char*)curPage_
) + sizeof(PageInfo
);
54 pageInfo
->hasFreeSpace_
=0;
56 db
->releaseAllocDatabaseMutex();
57 return data
+ sizeof(int);
61 //no space in curpage , get new page from database
62 pageInfo
= (PageInfo
*)db
->getFreePage(allocSize_
);
65 db
->releaseAllocDatabaseMutex();
66 printError(ErrNoMemory
,"No more free pages in the database");
69 printDebug(DM_Alloc
, "Chunk ID:%d Large Data Item newPage:%x",
71 int multiple
= os::floor(allocSize_
/ PAGE_SIZE
);
72 int offset
= ((multiple
+ 1) * PAGE_SIZE
);
74 pageInfo
->setPageAsUsed(offset
);
77 ((PageInfo
*)curPage_
)->nextPage_
= (Page
*) pageInfo
;
78 //Make this as current page
79 curPage_
= (Page
*) pageInfo
;
80 char* data
= ((char*)curPage_
) + sizeof(PageInfo
);
81 //TODO::check whether it is locked
83 db
->releaseAllocDatabaseMutex();
84 return data
+ sizeof(int);
88 void* Chunk::allocateFromFirstPage(Database
*db
, int noOfDataNodes
)
90 PageInfo
*pageIter
= ((PageInfo
*)firstPage_
);
91 printDebug(DM_Alloc
, "Chunk ID:%d. No free page in database",
93 printDebug(DM_Alloc
, "Scan from firstPage:%x for free nodes",
97 //scan from first page to locate a free node available
98 while(NULL
!= pageIter
)
100 data
= ((char*)pageIter
) + sizeof(PageInfo
);
101 if (pageIter
->hasFreeSpace_
== 1)
103 for (i
= 0; i
< noOfDataNodes
-1; i
++)
105 if (1 == *((int*)data
))
106 data
= data
+ allocSize_
;
109 if (i
!= noOfDataNodes
-1) break;
111 printDebug(DM_Alloc
, "Chunk ID: %d Page :%x does not have free nodes",
113 pageIter
= (PageInfo
*)((PageInfo
*) pageIter
)->nextPage_
;
115 if (NULL
== pageIter
) return NULL
;
116 printDebug(DM_Alloc
,"ChunkID:%d Scan for free node End:Page :%x",
119 return data
+ sizeof(int);
123 void* Chunk::allocateFromNewPage(Database
*db
)
125 DbRetVal ret
= db
->getAllocDatabaseMutex();
128 printError(ErrLockTimeOut
,"Unable to acquire alloc database Mutex");
131 //get a new page from db
132 Page
*page
= db
->getFreePage();
135 db
->releaseAllocDatabaseMutex();
138 printDebug(DM_Alloc
, "ChunkID:%d Normal Data Item newPage:%x",
140 //Initialize pageInfo for this new page
141 PageInfo
*pInfo
= (PageInfo
*)page
;
142 pInfo
->setPageAsUsed(0);
144 //create the link between old page and the newly created page
145 PageInfo
* pageInfo
= ((PageInfo
*)curPage_
);
146 pageInfo
->nextPage_
= page
;
148 //make this new page as the current page
151 char* data
= ((char*)page
) + sizeof(PageInfo
);
153 db
->releaseAllocDatabaseMutex();
154 return data
+ sizeof(int);
157 //Allocates memory to store data
158 //TODO::check whether it is locked before allocating.
159 //delete tuple will set the usedflag to true, but locks will be held
160 //till commit and it shall be rolledback.So make sure that it does not
161 //allocate deleted tuple which is yet to be commited.
163 void* Chunk::allocate(Database
*db
, DbRetVal
*status
)
165 PageInfo
* pageInfo
= ((PageInfo
*)curPage_
);
167 int noOfDataNodes
=os::floor((PAGE_SIZE
- sizeof(PageInfo
))/allocSize_
);
168 char *data
= ((char*)curPage_
) + sizeof(PageInfo
);
169 printDebug(DM_Alloc
, "Chunk::allocate id:%d curPage:%x noOfDataNodes:%d",
170 chunkID_
, curPage_
, noOfDataNodes
);
172 //1.scan through data list and find if any is free to use in current page
173 //2.If there is none then
174 // a) get new free page from db. set the prev->next to point
176 //4. b) initialize the free page to zero and get first data ptr.
177 //5.If there is one, return that
179 //For allocation more than PAGE_SIZE
180 if (0 == noOfDataNodes
)
182 data
= (char*) allocateForLargeDataSize(db
);
186 int ret
= getChunkMutex(db
->procSlot
);
189 if (status
!= NULL
) *status
= ErrLockTimeOut
;
190 printError(ErrLockTimeOut
,"Unable to acquire chunk Mutex");
193 int i
= noOfDataNodes
;
194 if (pageInfo
->hasFreeSpace_
== 1)
196 for (i
= 1; i
< noOfDataNodes
; i
++)
198 if (*((int*)data
) == 1) data
= data
+ allocSize_
;
203 printDebug(DM_Alloc
, "ChunkID:%d Node which might be free is %d",
205 //It comes here if the pageInfo->hasFreeSpace ==0
206 //or there are no free data space in this page
207 if (i
== noOfDataNodes
&& *((int*)data
) == 1)
210 printDebug(DM_Alloc
, "ChunkID:%d curPage does not have free nodes.", chunkID_
);
211 //there are no free data space in this page
212 pageInfo
->hasFreeSpace_
= 0;
213 if (chunkID_
== LockTableId
|| chunkID_
== TransHasTableId
)
215 data
= (char*) allocateFromFirstPage(db
, noOfDataNodes
);
218 data
= (char*) allocateFromNewPage(db
);
221 printError(ErrNoMemory
, "No memory in any of the pages:Increase db size");
222 if (status
!= NULL
) *status
= ErrNoMemory
;
228 data
= (char*) allocateFromNewPage(db
);
231 data
= (char*) allocateFromFirstPage(db
, noOfDataNodes
);
234 printError(ErrNoMemory
, "No memory in any of the pages:Increase db size");
235 if (status
!= NULL
) *status
= ErrNoMemory
;
239 releaseChunkMutex(db
->procSlot
);
243 releaseChunkMutex(db
->procSlot
);
244 return data
+ sizeof(int);
248 void* Chunk::allocateForLargeDataSize(Database
*db
, size_t size
)
250 //no need to take chunk mutexes for this, as we are taking alloc database mutex
251 int multiple
= os::floor(size
/ PAGE_SIZE
);
252 int offset
= ((multiple
+ 1) * PAGE_SIZE
);
253 PageInfo
* pageInfo
= ((PageInfo
*)curPage_
);
254 DbRetVal ret
= db
->getAllocDatabaseMutex();
257 printError(ErrLockTimeOut
,"Unable to acquire alloc database Mutex");
260 pageInfo
= (PageInfo
*)db
->getFreePage(allocSize_
);
261 if (NULL
== pageInfo
)
263 db
->releaseAllocDatabaseMutex();
264 printError(ErrNoMemory
,"No more free pages in the database:Increase db size");
267 printDebug(DM_VarAlloc
,"Chunk::allocate Large Data Item id:%d Size:%d curPage:%x ",
268 chunkID_
, size
, curPage_
);
269 //TODO:: logic pending
272 //REDESIGN MAY BE REQUIRED:Lets us live with this for now.
273 //what happens to the space lets say 10000 bytes is allocated
274 //it needs 2 pages,= 16000 bytes, 6000 bytes should not be wasted
275 //in this case.So need to take of this.
276 //Will be coded at later stage as this is developed to support
277 //undo logging and currently we shall assume that the logs generated
278 //wont be greater than PAGE_SIZE.
279 db
->releaseAllocDatabaseMutex();
286 void* Chunk::allocFromNewPageForVarSize(Database
*db
, size_t size
)
288 //Should be called only for data items <PAGE_SIZE
289 DbRetVal ret
= db
->getAllocDatabaseMutex();
292 printError(ErrLockTimeOut
,"Unable to acquire alloc database Mutex");
296 void *vnode
= varSizeFirstFitAllocate(size
);
299 db
->releaseAllocDatabaseMutex();
303 Page
*newPage
= db
->getFreePage();
304 db
->releaseAllocDatabaseMutex();
310 printDebug(DM_VarAlloc
, "ChunkID:%d New Page: %x ", chunkID_
, newPage
);
311 PageInfo
*pInfo
= (PageInfo
*) newPage
;
312 pInfo
->setPageAsUsed(0);
313 createDataBucket(newPage
, PAGE_SIZE
, size
);
315 ((PageInfo
*)curPage_
)->nextPage_
= newPage
;
317 char *data
= ((char*)newPage
) + sizeof(PageInfo
) + sizeof(VarSizeInfo
);
321 //Allocates from the current page of the chunk.
322 //Scans through the VarSizeInfo objects in the page and gets the free slot
323 void* Chunk::allocateFromCurPageForVarSize(size_t size
)
325 //Should be called only for data items <PAGE_SIZE
326 Page
*page
= ((PageInfo
*)curPage_
);
327 printDebug(DM_VarAlloc
, "Chunk::allocate Normal Data Item id:%d Size:%d curPage:%x ",
328 chunkID_
, size
, curPage_
);
329 VarSizeInfo
*varInfo
= (VarSizeInfo
*)(((char*)page
) +
331 while ((char*) varInfo
< ((char*)page
+ PAGE_SIZE
))
333 if (0 == varInfo
->isUsed_
)
335 if( size
+ sizeof(VarSizeInfo
) < varInfo
->size_
)
337 splitDataBucket(varInfo
, size
);
338 printDebug(DM_VarAlloc
, "Chunkid:%d splitDataBucket: Size: %d Item:%x ",
339 chunkID_
, size
, varInfo
);
340 return (char*)varInfo
+ sizeof(VarSizeInfo
);
342 else if (size
== varInfo
->size_
) {
343 varInfo
->isUsed_
= 1;
344 return (char *) varInfo
+ sizeof(VarSizeInfo
);
348 varInfo
= (VarSizeInfo
*)((char*)varInfo
+ sizeof(VarSizeInfo
)
354 //Allocates memory to store data of variable size
355 void* Chunk::allocate(Database
*db
, size_t size
, DbRetVal
*status
)
357 if (0 == size
) return NULL
;
358 //check if the size is more than PAGE_SIZE
359 //if it is more than the PAGE_SIZE, then allocate new
360 //page using database and then link the curPage to the
361 //newly allocated page
362 //if it is less than PAGE_SIZE, then check the curpage for
363 //free memory of specified size
364 //if not available, then scan from the firstPage for the free
367 //TODO::During the scan, merge nearby nodes if both are free
368 //if not available then allocate new page
370 size_t alignedSize
= os::align(size
);
372 int ret
= getChunkMutex(db
->procSlot
);
375 printError(ErrLockTimeOut
,"Unable to acquire chunk Mutex");
376 *status
= ErrLockTimeOut
;
379 if (alignedSize
> PAGE_SIZE
)
381 data
= allocateForLargeDataSize(db
, alignedSize
);
385 data
= allocateFromCurPageForVarSize(alignedSize
);
387 //No available spaces in the current page.
389 data
= allocFromNewPageForVarSize(db
, alignedSize
);
391 printError(ErrNoMemory
, "No memory in any of the pages:Increase db size");
392 if (status
!= NULL
) *status
= ErrNoMemory
;
396 releaseChunkMutex(db
->procSlot
);
400 //Assumes chunk mutex is already taken, before calling this
401 void* Chunk::varSizeFirstFitAllocate(size_t size
)
403 printDebug(DM_VarAlloc
, "Chunk::varSizeFirstFitAllocate size:%d firstPage:%x",
406 Page
*page
= ((PageInfo
*)firstPage_
);
407 size_t alignedSize
= os::align(size
);
410 VarSizeInfo
*varInfo
= (VarSizeInfo
*)(((char*)page
) + sizeof(PageInfo
));
411 while ((char*) varInfo
< ((char*)page
+ PAGE_SIZE
))
413 if (0 == varInfo
->isUsed_
)
415 if( alignedSize
+sizeof(VarSizeInfo
) < varInfo
->size_
)
417 splitDataBucket(varInfo
, alignedSize
);
418 return ((char*)varInfo
) + sizeof(VarSizeInfo
);
420 else if (alignedSize
== varInfo
->size_
) {
421 varInfo
->isUsed_
= 1;
422 printDebug(DM_VarAlloc
, "VarSizeFirstFitAllocate returning %x", ((char*)varInfo
) +sizeof(VarSizeInfo
));
423 return ((char *) varInfo
) + sizeof(VarSizeInfo
);
426 varInfo
= (VarSizeInfo
*)((char*)varInfo
+ sizeof(VarSizeInfo
)
429 printDebug(DM_VarAlloc
, "Chunk:This page does not have free data nodes page:%x", page
);
430 page
= ((PageInfo
*) page
)->nextPage_
;
435 void Chunk::freeForVarSizeAllocator(void *ptr
, int pslot
)
437 int ret
= getChunkMutex(pslot
);
440 printError(ErrLockTimeOut
,"Unable to acquire chunk Mutex");
443 VarSizeInfo
*varInfo
= (VarSizeInfo
*)((char*)ptr
- sizeof(VarSizeInfo
));
444 varInfo
->isUsed_
= 0;
445 printDebug(DM_VarAlloc
,"chunkID:%d Unset isUsed for %x", chunkID_
, varInfo
);
446 releaseChunkMutex(pslot
);
451 void Chunk::freeForLargeAllocator(void *ptr
, int pslot
)
453 //There will be max only one data element in a page.
454 //PageInfo is stored just before the data.
455 int ret
= getChunkMutex(pslot
);
458 printError(ErrLockTimeOut
,"Unable to acquire chunk Mutex");
461 PageInfo
*pageInfo
= (PageInfo
*)(((char*)
462 ptr
) - (sizeof(PageInfo
) + sizeof(int)));
463 PageInfo
*pInfo
= (PageInfo
*)firstPage_
, *prev
= (PageInfo
*)firstPage_
;
467 if (pInfo
== pageInfo
) {found
= true; break; }
469 pInfo
= (PageInfo
*)pInfo
->nextPage_
;
473 printError(ErrSysFatal
,"Page %x not found in page list:Logical error", pageInfo
);
474 releaseChunkMutex(pslot
);
477 prev
->nextPage_
= pageInfo
->nextPage_
;
478 pageInfo
->nextPageAfterMerge_
= NULL
;
479 pageInfo
->isUsed_
= 0;
480 os::memset(pageInfo
, 0 , allocSize_
);
481 pageInfo
->hasFreeSpace_
= 1;
482 releaseChunkMutex(pslot
);
486 //Frees the memory pointed by ptr
487 void Chunk::free(Database
*db
, void *ptr
)
491 freeForVarSizeAllocator(ptr
, db
->procSlot
);
494 int noOfDataNodes
=os::floor((PAGE_SIZE
- sizeof(PageInfo
)) / allocSize_
);
496 if (0 == noOfDataNodes
)
498 freeForLargeAllocator(ptr
, db
->procSlot
);
501 int ret
= getChunkMutex(db
->procSlot
);
504 printError(ErrLockTimeOut
,"Unable to acquire chunk Mutex");
507 //below is the code for freeing in fixed size allocator
509 //unset the used flag
510 *((int*)ptr
-1 ) = 0;
512 pageInfo
= getPageInfo(db
, ptr
);
513 if (NULL
== pageInfo
)
515 printError(ErrSysFatal
,"Probable Data corruption: pageInfo is NULL", pageInfo
);
516 releaseChunkMutex(db
->procSlot
);
519 //set the pageinfo where this ptr points
520 pageInfo
->hasFreeSpace_
= 1;
521 releaseChunkMutex(db
->procSlot
);
525 //returns the pageInfo of the page where this ptr points
526 //This works only if the data size is less than PAGE_SIZE
527 //If ptr points to data which is more than PAGE_SIZE,then
528 //calling this might lead to memory corruption
529 //Note:IMPORTANT::assumes db lock is taken before calling this
530 PageInfo
* Chunk::getPageInfo(Database
*db
, void *ptr
)
532 if (allocSize_
< PAGE_SIZE
- sizeof(PageInfo
)) {
533 int rem
= (long) ptr
% 8192;
534 return (PageInfo
*)(((char*)ptr
) - rem
);
536 //large size allocator
537 char *inPtr
= (char*)ptr
;
538 PageInfo
* pageInfo
= ((PageInfo
*)firstPage_
);
540 while( pageInfo
!= NULL
)
542 if (inPtr
> (char*) pageInfo
&& pageInfo
->nextPageAfterMerge_
>inPtr
)
544 pageInfo
= (PageInfo
*)pageInfo
->nextPage_
;
550 //If called on chunk used to store tuples, it returns the total number of rows
551 //present in the table
552 long Chunk::getTotalDataNodes()
555 if (0 == allocSize_
) //->variable size allocator
557 Page
*page
= ((PageInfo
*)firstPage_
);
560 VarSizeInfo
*varInfo
= (VarSizeInfo
*)(((char*)page
) + sizeof(PageInfo
));
561 while ((char*) varInfo
< ((char*)page
+ PAGE_SIZE
))
563 if (1 == varInfo
->isUsed_
) totalNodes
++;
564 varInfo
= (VarSizeInfo
*)((char*)varInfo
+ sizeof(VarSizeInfo
)
567 page
= ((PageInfo
*) page
)->nextPage_
;
572 //TODO::for large size allocator
573 if (allocSize_
>PAGE_SIZE
)//->each page has only one data node
575 Page
*page
= ((PageInfo
*)firstPage_
);
578 //current it page wise later this will done
579 if(1==*(int*)(((char*)page
)+sizeof(PageInfo
)))
581 page
= ((PageInfo
*) page
)->nextPage_
;
586 int noOfDataNodes
=os::floor((PAGE_SIZE
- sizeof(PageInfo
))/allocSize_
);
587 PageInfo
* pageInfo
= ((PageInfo
*)firstPage_
);
588 char *data
= ((char*)firstPage_
) + sizeof(PageInfo
);
590 while( pageInfo
!= NULL
)
592 data
= ((char*)pageInfo
) + sizeof(PageInfo
);
593 for (i
= 0; i
< noOfDataNodes
; i
++)
595 if (*((int*)data
) == 1) { totalNodes
++;}
596 data
= data
+ allocSize_
;
598 pageInfo
= (PageInfo
*)(((PageInfo
*)pageInfo
)->nextPage_
) ;
603 //TODO::for other type of allocators
606 PageInfo
* pageInfo
= ((PageInfo
*)firstPage_
);
607 PageInfo
* prevPage
= pageInfo
;
608 if (NULL
== pageInfo
)
612 pageInfo
= (PageInfo
*)pageInfo
->nextPage_
;
615 while( pageInfo
!= NULL
)
618 VarSizeInfo
*varInfo
= (VarSizeInfo
*)(((char*)pageInfo
) +
620 while ((char*) varInfo
< ((char*)pageInfo
+ PAGE_SIZE
))
622 if (1 == varInfo
->isUsed_
) {flag
=true; break;}
623 varInfo
= (VarSizeInfo
*)((char*)varInfo
+ sizeof(VarSizeInfo
)
627 printDebug(DM_VarAlloc
,"Freeing unused page in varsize allocator %x\n", pageInfo
);
628 prevPage
->nextPage_
= pageInfo
->nextPage_
;
629 pageInfo
->isUsed_
= 0;
632 pageInfo
= (PageInfo
*)(((PageInfo
*)pageInfo
)->nextPage_
) ;
633 printDebug(DM_VarAlloc
,"compact iter %x\n", pageInfo
);
635 }else if (allocSize_
< PAGE_SIZE
)
637 while( pageInfo
!= NULL
)
640 int noOfDataNodes
=os::floor((PAGE_SIZE
- sizeof(PageInfo
))/allocSize_
);
641 char *data
= ((char*)pageInfo
) + sizeof(PageInfo
);
642 for (int i
= 0; i
< noOfDataNodes
-1; i
++)
644 if (1 == *((int*)data
)) { flag
= true; break; }
645 data
= data
+allocSize_
;
648 printDebug(DM_Alloc
,"Freeing unused page in fixed allocator %x\n", pageInfo
);
649 prevPage
->nextPage_
= pageInfo
->nextPage_
;
650 pageInfo
->isUsed_
= 0;
653 pageInfo
= (PageInfo
*)(((PageInfo
*)pageInfo
)->nextPage_
) ;
654 printDebug(DM_Alloc
,"compact iter %x\n", pageInfo
);
660 int Chunk::totalPages()
662 //logic is same for variable size and for large data node allocator.
663 PageInfo
* pageInfo
= ((PageInfo
*)firstPage_
);
665 while( pageInfo
!= NULL
)
668 pageInfo
= (PageInfo
*)(((PageInfo
*)pageInfo
)->nextPage_
) ;
673 int Chunk::initMutex()
675 return chunkMutex_
.init("Chunk");
677 int Chunk::getChunkMutex(int procSlot
)
679 return chunkMutex_
.getLock(procSlot
);
681 int Chunk::releaseChunkMutex(int procSlot
)
683 return chunkMutex_
.releaseLock(procSlot
);
685 int Chunk::destroyMutex()
687 return chunkMutex_
.destroy();
689 void Chunk::splitDataBucket(VarSizeInfo
*varInfo
, size_t needSize
)
691 int remSpace
= varInfo
->size_
- sizeof(VarSizeInfo
) - needSize
;
692 varInfo
->isUsed_
= 1;
693 varInfo
->size_
= needSize
;
694 varInfo
= (VarSizeInfo
*)((char*)varInfo
+
695 sizeof(VarSizeInfo
) + varInfo
->size_
);
696 varInfo
->isUsed_
= 0;
697 varInfo
->size_
= remSpace
;
698 printDebug(DM_VarAlloc
, "Remaining space is %d\n", remSpace
);
703 void Chunk::createDataBucket(Page
*page
, size_t totalSize
, size_t needSize
)
705 VarSizeInfo
*varInfo
= (VarSizeInfo
*)(((char*)page
) + sizeof(PageInfo
));
706 varInfo
->isUsed_
= 0;
707 varInfo
->size_
= PAGE_SIZE
- sizeof(PageInfo
) - sizeof(VarSizeInfo
);
708 splitDataBucket(varInfo
, needSize
);
712 void Chunk::setChunkNameForSystemDB(int id
)
714 strcpy(chunkName
,ChunkName
[id
]);
719 printf(" <Chunk Id> %d </Chunk Id> \n",chunkID_
);
720 printf(" <TotalPages> %d </TotalPages> \n",totalPages());
721 printf(" <ChunkName > %s </ChunkName> \n",getChunkName());
722 printf(" <TotalDataNodes> %d </TotalDataNodes> \n",getTotalDataNodes());
723 printf(" <SizeOfDataNodes> %d </SizeOfDataNodes> \n",getSize());
724 printf(" <Allocation Type> ");
727 printf("FixedSizeAllocator ");
728 }else if(allocType_
==1)
730 printf("VariableSizeAllocator ");
733 printf("UnknownAllocator ");
736 printf("</Allocation Type>\n");