library/src/mmap/BP-MMapSlabAllocator.cc
// this routine attempts to defragment the slab allocator and coalesce individual
// chunks
this routine attempts to defragment the slab allocator and coalesce individual
chunks
this routine attempts to defragment the slab allocator and coalesce individual chunks
BP_ERROR_T BP_SlabAllocDefragAndUpdateFragIdx
(
		P_BP_MMAP_SLAB_ALLOCATOR allocator,
		P_BP_MMAP_SLAB_DEFRAG_INFO * defrag_info_out
)
{
	if(!allocator)
		return ERR_FAILURE;
	if(!allocator->entries_available)
		return ERR_FAILURE;
	if(!allocator->entry_count)
		return ERR_FAILURE;
	if(!allocator->entries_used)
		return ERR_FAILURE;
	BP_SlabAllocUpdateInfo(allocator, BP_TRUE);
	P_BP_MMAP_SLAB_DEFRAG_INFO defrag_info_entries = (P_BP_MMAP_SLAB_DEFRAG_INFO) calloc
	(
			sizeof(BP_MMAP_SLAB_ALLOCATOR_DEFRAG_INFO) * (allocator->group_alloc_n + 1),
			1
	);
	if(!defrag_info_entries)
		return ERR_FAILURE;
	size_t entries_till_first_group_hdr_n = 0;
	size_t entry_iter_n       = 0;
	size_t group_top_iter_n   = 0;
	size_t group_entry_iter_n = 0;
	BP_BOOL group_top_was_found = BP_FALSE;
	BP_BOOL next_is_grouped = BP_FALSE;
	BP_BOOL curr_is_trailing_free_space = BP_FALSE;
	size_t empty_chunks_before_first_group_n = 0;
	BP_SLAB_ALLOCATOR_ITER_LOOP_ALL(allocator)
	{
		if(!group_top_was_found)
		{
			if(BP_FLAG_IS_SET(allocator->curr_entry->flags, BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE))
			{
				empty_chunks_before_first_group_n++;
				continue;
			}
		}
		if(BP_FLAG_IS_SET(allocator->curr_entry->flags, BP_MMAP_SLAB_ENTRY_INFO_IS_GROUP_TOP))
		{
			group_top_iter_n++;
			defrag_info_entries[group_top_iter_n-1].group_alloc_top_ptr = allocator->curr_entry;
			if(BP_FLAG_IS_SET(allocator->curr_entry->flags, BP_MMAP_SLAB_ENTRY_INFO_NEXT_IS_GROUPED))
				next_is_grouped = BP_TRUE;
			printf("\n [+] - %u - Group Top %p", entry_iter_n, defrag_info_entries[group_top_iter_n-1].group_alloc_top_ptr);
			defrag_info_entries[group_top_iter_n-1].group_alloc_chunks_n++;
			if(!group_top_was_found)
			{
				defrag_info_entries[group_top_iter_n-1].is_first_group_entry = BP_TRUE;
				defrag_info_entries[group_top_iter_n-1].if_first_how_many_empty_before = empty_chunks_before_first_group_n;
				group_top_was_found=BP_TRUE;
			}
		}
		else
		{
			if(BP_FLAG_IS_SET(allocator->curr_entry->flags, BP_MMAP_SLAB_ENTRY_INFO_NEXT_IS_GROUPED))
			{
				printf("\n - %u - Advancing group iter!", entry_iter_n);
				defrag_info_entries[group_top_iter_n-1].group_alloc_chunks_n++;
			}
			else if(BP_FLAG_IS_SET(allocator->curr_entry->flags, BP_MMAP_SLAB_ENTRY_INFO_PREV_IS_GROUPED))
			{
				printf("\n - %u - Encountered final group entry!", entry_iter_n);
				defrag_info_entries[group_top_iter_n-1].group_alloc_chunks_n++;
			}
			else
			{
				if(group_top_was_found == BP_TRUE)
					defrag_info_entries[group_top_iter_n-1].trailing_available_alloc_n++;
				printf("\n - %u - Advancing available alloc iter.", entry_iter_n);
				next_is_grouped = BP_FALSE;
			}
		}
		if(!group_top_was_found)
			entries_till_first_group_hdr_n++;
		entry_iter_n++;
	}
	size_t n = 0;
	size_t j = 0;
	size_t adjusted_upward_move_value = 0;
	P_BP_MMAP_SLAB_ENTRY_HDR next_copy_location = NULL;
	if(group_top_was_found && allocator->group_alloc_n)
	for
	(
		;
		defrag_info_entries[n].group_alloc_top_ptr && (n < allocator->group_alloc_n);
		n++
	)
	{
		if(defrag_info_entries[n].is_first_group_entry)
		{
			if( allocator->top_entry != defrag_info_entries[n].group_alloc_top_ptr)
			{
				printf("\n [+] First chunk is moving.");
				memcpy
				(
					(void *) allocator->top_entry,
					defrag_info_entries[n].group_alloc_top_ptr,
					allocator->entry_size * defrag_info_entries[n].group_alloc_chunks_n
				);
				for(j=0; j < defrag_info_entries[n].group_alloc_chunks_n; j++)
				{
					defrag_info_entries[n].group_alloc_top_ptr[j].flags = 0;
					BP_SET_FLAG(defrag_info_entries[n].group_alloc_top_ptr[j].flags, BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE);
					BP_SET_FLAG(defrag_info_entries[n].group_alloc_top_ptr[j].flags, BP_MMAP_SLAB_ENTRY_INFO_CHUNK_MOVED);
				}
			}
			else
			{
				printf("\n [+] First chunk move not moving, only updating the copy location.");
			}
			next_copy_location = &allocator->top_entry
			[
				 defrag_info_entries[n].group_alloc_chunks_n
			];
			defrag_info_entries[n].next_group_write_start_ptr = next_copy_location;
		}
		else
		{
			if(next_copy_location == defrag_info_entries[n].group_alloc_top_ptr)
			{
				printf("\n [+] Secondary chunk move not moving, only updating the copy location.");
				next_copy_location = &defrag_info_entries[n].group_alloc_top_ptr
				[
					 defrag_info_entries[n].group_alloc_chunks_n
				];
				defrag_info_entries[n].next_group_write_start_ptr = next_copy_location;
			}
			else
			{
				printf("\n [+] Secondary chunk is moving to new location");
				defrag_info_entries[n].group_alloc_top_ptr_moved = next_copy_location;
				memcpy
				(
					(void *) next_copy_location,
					defrag_info_entries[n].group_alloc_top_ptr,
					allocator->entry_size * defrag_info_entries[n].group_alloc_chunks_n
				);
				for(j=0; j < defrag_info_entries[n].group_alloc_chunks_n; j++)
				{
					defrag_info_entries[n].group_alloc_top_ptr[j].flags = 0;
					BP_SET_FLAG(defrag_info_entries[n].group_alloc_top_ptr[j].flags, BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE);
					BP_SET_FLAG(defrag_info_entries[n].group_alloc_top_ptr[j].flags, BP_MMAP_SLAB_ENTRY_INFO_CHUNK_MOVED);
				}
				next_copy_location = &defrag_info_entries[n].group_alloc_top_ptr
				[
					 defrag_info_entries[n].group_alloc_chunks_n
				];
				defrag_info_entries[n].next_group_write_start_ptr = next_copy_location;
			}
		}
	}
	if(!group_top_was_found)
		return ERR_FAILURE;
	if(!defrag_info_out)
		free(defrag_info_entries);
	else
		*defrag_info_out = defrag_info_entries;
	return ERR_SUCCESS;
}
BP_ERROR_T BP_SlabAllocDefragAndUpdateFragIdx ( P_BP_MMAP_SLAB_ALLOCATOR allocator , P_BP_MMAP_SLAB_DEFRAG_INFO * defrag_info_out ) { if ( ! allocator ) return ERR_FAILURE ; if ( ! allocator -> entries_available ) return ERR_FAILURE ; if ( ! allocator -> entry_count ) return ERR_FAILURE ; if ( ! allocator -> entries_used ) return ERR_FAILURE ; BP_SlabAllocUpdateInfo ( allocator , BP_TRUE ) ; P_BP_MMAP_SLAB_DEFRAG_INFO defrag_info_entries = ( P_BP_MMAP_SLAB_DEFRAG_INFO ) calloc ( sizeof ( BP_MMAP_SLAB_ALLOCATOR_DEFRAG_INFO ) * ( allocator -> group_alloc_n + 1 ) , 1 ) ; if ( ! defrag_info_entries ) return ERR_FAILURE ; size_t entries_till_first_group_hdr_n = 0 ; size_t entry_iter_n = 0 ; size_t group_top_iter_n = 0 ; size_t group_entry_iter_n = 0 ; BP_BOOL group_top_was_found = BP_FALSE ; BP_BOOL next_is_grouped = BP_FALSE ; BP_BOOL curr_is_trailing_free_space = BP_FALSE ; size_t empty_chunks_before_first_group_n = 0 ; BP_SLAB_ALLOCATOR_ITER_LOOP_ALL ( allocator ) { if ( ! group_top_was_found ) { if ( BP_FLAG_IS_SET ( allocator -> curr_entry -> flags , BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE ) ) { empty_chunks_before_first_group_n ++ ; continue ; } } if ( BP_FLAG_IS_SET ( allocator -> curr_entry -> flags , BP_MMAP_SLAB_ENTRY_INFO_IS_GROUP_TOP ) ) { group_top_iter_n ++ ; defrag_info_entries [ group_top_iter_n - 1 ] . group_alloc_top_ptr = allocator -> curr_entry ; if ( BP_FLAG_IS_SET ( allocator -> curr_entry -> flags , BP_MMAP_SLAB_ENTRY_INFO_NEXT_IS_GROUPED ) ) next_is_grouped = BP_TRUE ; printf ( " \n " , entry_iter_n , defrag_info_entries [ group_top_iter_n - 1 ] . group_alloc_top_ptr ) ; defrag_info_entries [ group_top_iter_n - 1 ] . group_alloc_chunks_n ++ ; if ( ! group_top_was_found ) { defrag_info_entries [ group_top_iter_n - 1 ] . is_first_group_entry = BP_TRUE ; defrag_info_entries [ group_top_iter_n - 1 ] . if_first_how_many_empty_before = empty_chunks_before_first_group_n ; group_top_was_found = BP_TRUE ; } } else { if ( BP_FLAG_IS_SET ( allocator -> curr_entry -> flags , BP_MMAP_SLAB_ENTRY_INFO_NEXT_IS_GROUPED ) ) { printf ( " \n " , entry_iter_n ) ; defrag_info_entries [ group_top_iter_n - 1 ] . group_alloc_chunks_n ++ ; } else if ( BP_FLAG_IS_SET ( allocator -> curr_entry -> flags , BP_MMAP_SLAB_ENTRY_INFO_PREV_IS_GROUPED ) ) { printf ( " \n " , entry_iter_n ) ; defrag_info_entries [ group_top_iter_n - 1 ] . group_alloc_chunks_n ++ ; } else { if ( group_top_was_found == BP_TRUE ) defrag_info_entries [ group_top_iter_n - 1 ] . trailing_available_alloc_n ++ ; printf ( " \n " , entry_iter_n ) ; next_is_grouped = BP_FALSE ; } } if ( ! group_top_was_found ) entries_till_first_group_hdr_n ++ ; entry_iter_n ++ ; } size_t n = 0 ; size_t j = 0 ; size_t adjusted_upward_move_value = 0 ; P_BP_MMAP_SLAB_ENTRY_HDR next_copy_location = NULL ; if ( group_top_was_found && allocator -> group_alloc_n ) for ( ; defrag_info_entries [ n ] . group_alloc_top_ptr && ( n < allocator -> group_alloc_n ) ; n ++ ) { if ( defrag_info_entries [ n ] . is_first_group_entry ) { if ( allocator -> top_entry != defrag_info_entries [ n ] . group_alloc_top_ptr ) { printf ( " \n " ) ; memcpy ( ( void * ) allocator -> top_entry , defrag_info_entries [ n ] . group_alloc_top_ptr , allocator -> entry_size * defrag_info_entries [ n ] . group_alloc_chunks_n ) ; for ( j = 0 ; j < defrag_info_entries [ n ] . group_alloc_chunks_n ; j ++ ) { defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags = 0 ; BP_SET_FLAG ( defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags , BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE ) ; BP_SET_FLAG ( defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags , BP_MMAP_SLAB_ENTRY_INFO_CHUNK_MOVED ) ; } } else { printf ( " \n " ) ; } next_copy_location = & allocator -> top_entry [ defrag_info_entries [ n ] . group_alloc_chunks_n ] ; defrag_info_entries [ n ] . next_group_write_start_ptr = next_copy_location ; } else { if ( next_copy_location == defrag_info_entries [ n ] . group_alloc_top_ptr ) { printf ( " \n " ) ; next_copy_location = & defrag_info_entries [ n ] . group_alloc_top_ptr [ defrag_info_entries [ n ] . group_alloc_chunks_n ] ; defrag_info_entries [ n ] . next_group_write_start_ptr = next_copy_location ; } else { printf ( " \n " ) ; defrag_info_entries [ n ] . group_alloc_top_ptr_moved = next_copy_location ; memcpy ( ( void * ) next_copy_location , defrag_info_entries [ n ] . group_alloc_top_ptr , allocator -> entry_size * defrag_info_entries [ n ] . group_alloc_chunks_n ) ; for ( j = 0 ; j < defrag_info_entries [ n ] . group_alloc_chunks_n ; j ++ ) { defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags = 0 ; BP_SET_FLAG ( defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags , BP_MMAP_SLAB_ENTRY_INFO_AVAILABLE ) ; BP_SET_FLAG ( defrag_info_entries [ n ] . group_alloc_top_ptr [ j ] . flags , BP_MMAP_SLAB_ENTRY_INFO_CHUNK_MOVED ) ; } next_copy_location = & defrag_info_entries [ n ] . group_alloc_top_ptr [ defrag_info_entries [ n ] . group_alloc_chunks_n ] ; defrag_info_entries [ n ] . next_group_write_start_ptr = next_copy_location ; } } } if ( ! group_top_was_found ) return ERR_FAILURE ; if ( ! defrag_info_out ) free ( defrag_info_entries ) ; else * defrag_info_out = defrag_info_entries ; return ERR_SUCCESS ; }
this routine attempts to defragment the slab allocator and coalesce individual
chunks
this routine attempts to defragment the slab allocator and coalesce individual chunks
// ensure we have an allocator // there is nothing to coalesce if there are no available entries // there is nothing to coalese if there are no entries // there is nothing to coalesce if there are no used entries // update allocation info // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Allocate Defrag Info Structures on Heap %%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // Allocate space with a trailing entry.  The trailing entry is set for iterative purposes // as a trunctating element. // ensure we have entries allocated // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Loop 1: Calculate Move Positions %%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // this holds the number of entries which were passed till we found // a group. // iterative counter // Indicator that a group top was found // Indicator for whether or not the next entry in the list is grouped with the // current group top header. // flag to indicat whether or not entries are trailing free allocs // number of empty chunks found before first group entry // Loop through all entries, updating the allocator with relevant data on each loop count. // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Keep Track of Empties %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // ensure we have a group top // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Perform Counts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // increment group top iter on detection of group top iteratoro // set the defrag top pointer // if the next is part of a group, indicate so here // display group top message // increase the allocated chunk count // ensure you have a group top // mark as first // set the empty chunks entry // set the group top indicator toggle // verbosity // increase the allocated chunk count // verbosity // increase the allocated chunk count // verbosity // remove the presumption that the next entry is grouped // if a group top was not found, go ahead and update here // increment the iterator // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Now Coalesce Freespace Based On Gathered Info %%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // declare iterator for tracking info entry indexes // this is the iterator used for marking cleared chunks as available // this is used to determine the subtractive distance between moved chunks, and // allows // this after the initial move (first top entry) this will be set to the // value of the next write position. // Enter loop only if a group top was found.  Loop through all entries and push entries up // through existing freespace, keeping track of new freespace created during these pushes, so // as to provide a record for iteratively pushing distances dynamically. // if this is the FIRST group allocated in the slab, we need to // examine the struct.if_first_how_many_empty_before member and // push (aka move) the items up. // only move data if it's actually being moved // verbosity // copy in information // mark all cleared chunks as available // verbosity // set the next copy location as the bottom of the moved chunks // save the next copy location // verbosity // set the next copy location // save the next copy location // verbosity // set the movement indicator // copy in information // mark all cleared chunks as available // set the next copy location // save the next copy location // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%% Exit Routine %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // ensure that the group top was found // If the dev has requested info out, provide it, if not just destroy the // data before exiting. // return indicating success