/* ******************************************************************************* * Copyright (c) 1996 Martin Poole * ******************************************************************************* ** ** WARNING !! WARNING !! WARNING !! WARNING !! WARNING !! WARNING !! ** ** Any changes to be made to this file should first be checked with ** mplib1 source control for library integrity. ** ** mplib1 source control can be reached at mplib1@quatermass.co.uk ** * * $Source: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/bpo_alloc.c,v $ * $Author: mpoole $ * $Date: 2002/10/07 09:37:36 $ * $Revision: 1.2 $ * ******************************************************************************* * * Change History * * $Log: bpo_alloc.c,v $ * Revision 1.2 2002/10/07 09:37:36 mpoole * Initial checkin of mplib1-3.1.0 * * Revision 1.1 2002/10/07 09:36:52 mpoole * Initial checkin of mplib1-3.1.0 * * ******************************************************************************* */ #ident "$Header: /home/cvs/cvsroot/onelan/onelan/src/mplib1/libsrc/bpo_alloc.c,v 1.2 2002/10/07 09:37:36 mpoole Exp $" /* ------------------------------------------------------------------ Include files ------------------------------------------------------------------ */ #include #include #include #include #include #include #include #include #include #include #include #include #include "../include/bpo_init_internal.h" #include "../include/bpo_alloc_private.h" #include #ifdef SHALLOC_DEBUG #include #endif /* ------------------------------------------------------------------ defines ------------------------------------------------------------------ */ static char shalloc_name[] = "shalloc"; #ifdef SHALLOC_DEBUG static char alloc_debug_str[]="BPO_ALLOC_DEBUG"; static int bpo_alloc_debug=0; #endif /* ------------------------------------------------------------------ Code starts here ------------------------------------------------------------------ */ static off_t init_sth( struct shalloc_track_head *sthp, int num_tracks, char *seg_base ) { struct shalloc_track *stp; int t; sthp->lno_me = GOFF( seg_base, sthp ); sthp->next_track_head = 0; sthp->num_tracks = num_tracks; sthp->num_empty = num_tracks; sthp->sth_flags = 0; sthp->head_and_tracks = sizeof(struct shalloc_track_head) + num_tracks * sizeof(struct shalloc_track); stp = (struct shalloc_track *)( sthp + 1 ); for (t=0; tsh_off = 0; stp->sh_size = 0; stp++; } return(sthp->lno_me); } static off_t remove_ptr_from_list( void *freep, size_t *free_sz, char *seg_base, struct shalloc_base *sh_base, struct shalloc_track_head *sthp ) { /* In this routine we must take the provided pointer and size and place them in an empty entry on the given list */ struct shalloc_track *stp; int t; off_t moff; moff = GOFF( seg_base, freep ); do { stp = GPTR( sthp, sizeof(struct shalloc_track_head)); for(t=0; tnum_tracks; t++) { if (stp->sh_off == moff) { /* Dat's mine ! */ sthp->num_empty++; *free_sz = stp->sh_size; stp->sh_off = 0; stp->sh_size = 0; return(moff); } stp++; } } while ( (sthp = GRPTR( sthp, sthp->next_track_head )) ); return(0); } static off_t find_sz_in_free_list( size_t free_sz, char *seg_base, struct shalloc_base *sh_base ) { /* In this routine we must find an entry on the free list of at least the required size, splitting the found entry if it is too large */ struct shalloc_track_head *sthp; struct shalloc_track *stp; off_t my_off; size_t my_sz; int t; sthp = GPTR( seg_base, sh_base->lno_first_free ); do { stp = GPTR( sthp, sizeof(struct shalloc_track_head)); for(t=0; tnum_tracks; t++) { if (stp->sh_off != 0 && stp->sh_size >= free_sz) { /* Remember the size and offset, since this free shalloc_track is now free */ #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr, "find_sz_in_free_list: Found %lx %x (for %x)\n", stp->sh_off, stp->sh_size, free_sz ); #endif my_off = stp->sh_off; my_sz = stp->sh_size; /* Dat's mine ! */ if ( (free_sz + MIN_SHALLOC_SIZE) <= my_sz ) { #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr,"find_sz_in_free_list: Big enough to reduce\n"); #endif stp->sh_off += free_sz; stp->sh_size -= free_sz; my_sz = free_sz; }else { stp->sh_off = (off_t)0; stp->sh_size = (size_t)0; sthp->num_empty++; } /* return the various found elements */ return(my_off); } stp++; } #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr, "find_sz_in_free_list: Got to move to next free %lx\n", sthp->next_track_head ); #endif sthp = GRPTR( sthp, sthp->next_track_head ); #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr, "find_sz_in_free_list: Moving to head %p\n", sthp ); #endif } while (sthp); return(0); } static int shfree_merge( char *seg_base, struct shalloc_base *sh_base, char *freep, size_t freesz, int recurse_flag ) { /* This routine attempts to merge the given block with an adjacent one on the free list. Either the preceding block or the following block. If we succeed, the entry does not need to be put on the free list since we jave adjusted the entry we found. If we fail then the entry will probably be put on the free list, but that's not our job. Note: if the block we are freeing is in-between two already free blocks then we want to amalgamate all three into a single block. Since we do not know in advance which block (if any) is going to be first we need some mechanism to ensure that there is only the one block left. If we find an adjacent block, we adjust that block to include the freeing segment. We then call ourself(if the recurse_flag is not true), with the recurse_flag set to true, and let the routine search for the other side of the freeing block. If found then it will have acquired our found block so we can clear it. Either way the merge is complete, and we can return. */ struct shalloc_track *stp; struct shalloc_track_head *sthp; int t,rv=0; char *nextb, *prevb, *thisb; nextb = freep + freesz; sthp = GRPTR( sh_base, sh_base->lno_first_free ); do { stp = GPTR( sthp, sizeof(struct shalloc_track_head)); for(t=0; tnum_tracks; t++) { if ( stp->sh_off != 0 ) { /* Check this one */ thisb = GPTR( seg_base, stp->sh_off ); prevb = thisb + stp->sh_size; if ( freep == prevb ) { /* Ah, this stp immediately precedes the block being freed */ stp->sh_size += freesz; /* Now adjust the block we think we're freeing */ if ( recurse_flag==0 && shfree_merge( seg_base, sh_base, thisb, stp->sh_size, 1 ) == 1) { /* this block was merged into one following it. */ stp->sh_off = 0; stp->sh_size = 0; sthp->num_empty ++; } return(1); }else if ( thisb == nextb ) { /* the freed item is before the next bit */ stp->sh_size += freesz; stp->sh_off -= freesz; if ( recurse_flag == 0 && shfree_merge( seg_base, sh_base, freep, stp->sh_size, 1 ) == 1) { /* this block was merged into one preceding it */ stp->sh_off = 0; stp->sh_size = 0; sthp->num_empty ++; } return(1); } } stp++; } } while ( (sthp = GRPTR( sthp, sthp->next_track_head )) ); return(rv); } static int put_on_sh_list( void *freep, size_t free_sz, char *seg_base, struct shalloc_base *sh_base, struct shalloc_track_head *sthp ) { /* In this routine we must take the provided pointer and size and place them in an empty entry on the given list */ struct shalloc_track *stp; int t; do { stp = GPTR( sthp, sizeof(struct shalloc_track_head)); for(t=0; tnum_tracks; t++) { if (stp->sh_off == 0) { /* Dat's mine ! */ sthp->num_empty--; stp->sh_off = GOFF( seg_base, freep ); stp->sh_size = free_sz; return(stp->sh_off); } stp++; } } while ( (sthp = GRPTR( sthp, sthp->next_track_head )) ); return(0); } struct sodb_resource * shalloc_init( void *seg_base, off_t shalloc_base_off, size_t shalloc_sz ) { /* set up a base, and a pair of (track_heads + array of tracks) */ struct shalloc_base *sh_base; struct shalloc_track_head *free_head,*used_head, *thead; size_t sz2; sh_base = GPTR(seg_base, shalloc_base_off); b_Init( &sh_base->sb_lock ); b_Lock( &sh_base->sb_lock ); #ifdef SHALLOC_DEBUG bpo_alloc_debug = get_config_flag( alloc_debug_str ); #endif sh_base->lno_me = shalloc_base_off; sh_base->sh_size = shalloc_sz; sh_base->emergency_used.sh_off = 0; sh_base->emergency_used.sh_size = 0; Sstrcpy(sh_base->shalloc_name, shalloc_name ); sh_base->shalloc_resource.res_off = shalloc_base_off; bpo_Init_Node_Raw( &sh_base->shalloc_resource.res_node, seg_base, sh_base->shalloc_name, &sh_base->shalloc_resource ); used_head = (struct shalloc_track_head *)(sh_base +1); sh_base->lno_first_used = init_sth( used_head, STD_NUM_TRACK_BLKS, seg_base ); free_head = GPTR( used_head, (off_t)(used_head->head_and_tracks) ); sh_base->lno_first_free = init_sth( free_head, STD_NUM_TRACK_BLKS, seg_base ); /* We now need to know how much is left, and to put this as one first of the free entries. */ thead = GPTR( free_head, (off_t)(free_head->head_and_tracks) ); sz2 = (size_t)GOFF( thead, (char *)sh_base + shalloc_sz ); put_on_sh_list( (void *)thead, sz2, seg_base, sh_base, free_head ); b_Unlock( &sh_base->sb_lock ); return( &sh_base->shalloc_resource ); } static off_t shalloc_sth( void *seg_base, struct shalloc_base *sh_base, int num_tracks ) { off_t my_off; size_t how_much; how_much = sizeof(struct shalloc_track_head) + num_tracks * sizeof(struct shalloc_track); my_off = find_sz_in_free_list( how_much, seg_base, sh_base ); return(my_off); } void * shalloc( const void *hint, size_t how_much ) { /* First we check that the hint is in the permitted region */ char *seg_base; struct shalloc_base *sh_base; struct shalloc_track_head *free_head,*used_head; off_t my_off; void *ptr; seg_base = Get_SODB_Base( hint ); if (seg_base == NULL) return(NULL); sh_base = Find_SODB_Resource( seg_base, shalloc_name ); if (sh_base==NULL) return(NULL); #ifdef SHALLOC_DEBUG bpo_alloc_debug = get_config_flag( alloc_debug_str ); #endif b_Lock( &sh_base->sb_lock ); free_head = GRPTR( sh_base, sh_base->lno_first_free ); used_head = GRPTR( sh_base, sh_base->lno_first_used ); /* now walk the free list looking for the smallest/first free lump that meets our requirements */ /* adjust the size we require to account for the off_t that preceeds it */ how_much += sizeof(off_t); /* Now adjust the size to the next largest MIN_SHALLOC_SIZE */ how_much = (how_much + (MIN_SHALLOC_SIZE - 1)) & MIN_SHALLOC_MASK; #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr,"shalloc: find %x free in SODB %p\n", how_much, sh_base ); #endif my_off = find_sz_in_free_list( how_much, seg_base, sh_base ); if (my_off) { /* Generate the pointer */ ptr = GPTR( seg_base, my_off ); /* Now try and place this item on the used list */ if (put_on_sh_list( ptr, how_much, seg_base, sh_base, used_head )==0) { off_t sth_off; /* no spare entries on used list, shalloc another sth */ sth_off = shalloc_sth( seg_base, sh_base, STD_NUM_TRACK_BLKS ); if (sth_off) { struct shalloc_track_head *sthp; sthp = GPTR( seg_base, sth_off ); init_sth( sthp, STD_NUM_TRACK_BLKS, seg_base ); sthp->next_track_head = sh_base->lno_first_used; sh_base->lno_first_used = sth_off; used_head = GPTR( seg_base, sth_off ); put_on_sh_list( ptr, how_much, seg_base, sh_base, used_head ); }else { /* If we reach here then we are facing impending death of the shalloc system in this SODB. Since we have found the requested amount of memory, we will return it, and save the details in the emergency section of the shalloc_base structure */ sh_base->emergency_used.sh_off = my_off; sh_base->emergency_used.sh_size = how_much; } } /* mark the first off_t with its own offset */ #ifdef SHALLOC_DEBUG if (bpo_alloc_debug) fprintfile(stderr, "shalloc: Marking %p(%lx)\n", ptr, my_off ); #endif *(off_t *)ptr = my_off; #ifdef CAN_ADD_OFF_T_TO_VOID_PTR ptr += sizeof(off_t); #else ptr = (void *)((char*)ptr + sizeof(off_t)); #endif }else ptr = NULL; b_Unlock( &sh_base->sb_lock ); if (ptr) memset( ptr, '\0', how_much - sizeof(off_t) ); return(ptr); } void shfree( void *freep ) { /* First we check that the hint is in the permitted region */ char *seg_base; struct shalloc_base *sh_base; struct shalloc_track_head *free_head,*used_head; size_t found_sz; off_t moff,my_off,*moffp; seg_base = Get_SODB_Base( freep ); if (seg_base == NULL) return; sh_base = Find_SODB_Resource( seg_base, shalloc_name ); if (sh_base==NULL) return; #ifdef SHALLOC_DEBUG bpo_alloc_debug = get_config_flag( alloc_debug_str ); #endif b_Lock( &sh_base->sb_lock ); free_head = GRPTR( sh_base, sh_base->lno_first_free ); used_head = GRPTR( sh_base, sh_base->lno_first_used ); moffp = freep; moffp--; /* point to offset stored before */ moff = GOFF( seg_base, moffp ); if ( *moffp != moff ) /* Is this really an allocated object ? */ { b_Unlock( &sh_base->sb_lock ); #ifdef SHALLOC_DEBUG fprintfile( stderr, "shfree: Item %p(%lx) incorrect prior offset %lx\n", moffp, *moffp, moff ); #endif return; } my_off = remove_ptr_from_list( moffp, &found_sz, seg_base, sh_base, used_head ); if (my_off) { /* Now we try and merge this item with any adjacent free segment */ freep = GPTR( seg_base, my_off ); if (shfree_merge( seg_base, sh_base, freep, found_sz, 0 ) == 0) { if (put_on_sh_list( moffp, found_sz, seg_base, sh_base, free_head ) == 0) { /* no free entries, turn this into a free entry */ int nt; struct shalloc_track_head *sthp; sthp = (struct shalloc_track_head *)freep; nt = (found_sz - sizeof(struct shalloc_track_head)) / sizeof(struct shalloc_track); if (nt) { /* can be used for free segments */ init_sth( sthp, nt, seg_base ); sthp->next_track_head = sh_base->lno_first_free; sh_base->lno_first_free = my_off; } } } }else { #ifdef SHALLOC_DEBUG fprintfile( stderr, "shfree: Item @ %p(%lx) is not in free list\n", moffp, moff ); #endif } b_Unlock( &sh_base->sb_lock ); return; } char * bpo_strdup( const void *hint, const char *s1 ) { char *rv; rv = shalloc( hint, (size_t)(Sstrlen(s1) + 1) ); if (rv) Sstrcpy( rv, s1 ); return(rv); } off_t bpo_strdup_offset( const void *hint, const char *s1 ) { char *rv; off_t rvo; rv = shalloc( hint, (size_t)(Sstrlen(s1) + 1) ); if (rv) { Sstrcpy( rv, s1 ); rvo = Get_SODB_Offset( rv ); }else rvo = (off_t)0; return(rvo); } /* -- End of File -- */