added performance improvement in find_slots routine to skip full bit map words in...
[keystone-rtos/netapi.git] / ti / runtime / hplib / src / bm_alloc.c
1 #include <stdlib.h>
2 #include <stdint.h>
3 /***********************************************************************
4  * FILE: bm_alloc.c
5  * Purpose:  Memory allocator which uses a bit-map for book keeping purposes
6  * to keep track of used and un-used memory locations
7  ***********************************************************************
8  * FILE: bm_alloc.c
9  * 
10  * DESCRIPTION:  Memory allocator which uses a bit-map for book keeping purposes
11  * to keep track of used and un-used memory locations
12  * 
13  * REVISION HISTORY:
14  *
15  *  Copyright (c) Texas Instruments Incorporated 2013
16  * 
17  *  Redistribution and use in source and binary forms, with or without 
18  *  modification, are permitted provided that the following conditions 
19  *  are met:
20  *
21  *    Redistributions of source code must retain the above copyright 
22  *    notice, this list of conditions and the following disclaimer.
23  *
24  *    Redistributions in binary form must reproduce the above copyright
25  *    notice, this list of conditions and the following disclaimer in the 
26  *    documentation and/or other materials provided with the   
27  *    distribution.
28  *
29  *    Neither the name of Texas Instruments Incorporated nor the names of
30  *    its contributors may be used to endorse or promote products derived
31  *    from this software without specific prior written permission.
32  *
33  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
34  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
35  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
36  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
37  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
38  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
39  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
40  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
41  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
42  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
43  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44  *  *****************************/
46 #define PSZ_DEF 256  /* defatult Page Size */
48 /* Internal structure used to manage the alloc/free memory region */
49 typedef struct BM_MALLOC_STATE_Tag
50 {
51     /* this must point to a multi-proc shararable area, typically at the start
52        of the memory area to be managed. the pointer is in this process addr space.
53        Must be at least of size maxsize/(NPAGES*8*4) */
54     uint32_t *bmap;  
55     /* this is the pointer to the memory area to be managed, in this processes addr space */
56     uint8_t *pBase;
57     /* size of the memory area */
58     int maxsize;
59     /* number of pages in the memory area */
60     int NPAGES;
61     
62     /* the page size to use  should be power of 2*/
63     int PSZ;
64 } BM_MALLOC_STATE_T;
67 static inline int bmOff( BM_MALLOC_STATE_T *p, int wordpos, int bitpos)
68 {
69    return  (wordpos*8*sizeof(uint32_t))*p->PSZ +  (bitpos&0x1f)*p->PSZ;
71 }
72 static inline int bmToWordBit( BM_MALLOC_STATE_T *p, int off,  int * pbitpos)
73 {
74     int temp=  off/p->PSZ;
75     int wp = temp/(8*sizeof(uint32_t));
76     *pbitpos = temp - wp*(8*sizeof(uint32_t));
77     return wp;    
78 }
79 static inline void bmSetBits(BM_MALLOC_STATE_T *p,int sw,int sb, int ew, int eb, int val)
80 {
81 int i;
82 int j;
84     if( ew>sw)
85     {
86         //1st word
87         if (val)
88             for(j=sb;j<32;j++) p->bmap[sw] |= 1<< (31-j);
89         else
90             for(j=sb;j<32;j++) p->bmap[sw] &= ~(1<<(31-j));
91      
92         for(i=sw+1; i< ew; i++)
93         {
94             if(val)
95                 p->bmap[i]= 0xffffffff;
96             else
97                 p->bmap[i]= 0x00000000;
98         }
99         //last word
100         if (val)
101         {
102             for(j=0;j<=eb;j++) 
103                 p->bmap[ew] |= 1<< (31-j);
104         }
105         else
106         {
107             for(j=0;j<=eb;j++)
108                 p->bmap[ew] &= ~(1<<(31-j));
109         }
110     }
111     else //special case of allocation/free just in one word
112     {
113         if (val)
114         {
115             for(j=sb;j<=eb;j++) 
116                 p->bmap[sw] |= 1<< (31-j);
117         }
118         else
119         {
120             for(j=sb;j<=eb;j++)
121                 p->bmap[sw] &= ~(1<<(31-j));
122         }
123     }
126 /* find sz worth of consecutive free slots using first-fit */
127 static int inline bmFindSlots(BM_MALLOC_STATE_T *p, uint32_t size)
129     int i,j, flag,c;
130     int szinpages= size/p->PSZ;
131     uint32_t * pW = &p->bmap[0];
132     int wordpos=0;
133     int bitpos=0;
134     int ewordpos=0;
135     int ebitpos=0;
136     flag=0;
137     if ((szinpages * p->PSZ) < size) szinpages+=1;
138     for(i=0,c=0;i<p->NPAGES/(8*sizeof(uint32_t)) && (c< szinpages) ;)
139     {
140         if ((!flag) && (*pW == 0xffffffff)) {pW+=1;i+=1;continue;}
141         for(j=0;j<(8*sizeof(uint32_t));j++)
142         {
143             if (!flag)
144             { 
145                 if (*pW & ( 1<<(31-j)) ) continue;
146                 c=1;
147                 flag= 1;
148                 wordpos = ewordpos=i;
149                 bitpos= ebitpos=j;
150             }
151             else
152             {
153                 if (c==szinpages) break; //skipping rest of inner loop
154                 if(*pW & (1<<(31-j)) )
155                 {
156                     //not large enough
157                     c=0;
158                     flag=0;
159                     continue;
160                 }
161                 c +=1;
162                 ewordpos=i;
163                 ebitpos=j;
164             }
165         }
166         pW+=1;
167         i+=1;
168     }
169     if (c!=szinpages)
170     {
171         return -1;
172     }
173     //got it
174     bmSetBits(p,wordpos,bitpos, ewordpos, ebitpos, 1);
175     return bmOff(p,wordpos,bitpos);
181 /********************************************************************
182 * FUNCTION PURPOSE: Malloc a block of memory from memory area
183 ********************************************************************
184 * DESCRIPTION:  Malloc a block from the region whose state is in blob
185 * Note:in multi proc/multi thread, caller needs to do a critical section
186  ********************************************************************/
187 uint8_t* bmAlloc(void* blob, uint32_t size)
189     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) blob;
190     int off;
191     
192     if (size> pCtx->maxsize) return NULL;
194     off= bmFindSlots(pCtx,size);
195     if (off<0)
196         return NULL;
197      return &pCtx->pBase[off];
199 /********************************************************************
200 * FUNCTION PURPOSE: Free back  a block of memory from allocated memory 
201 *                   retion
202 ********************************************************************
203 * DESCRIPTION:  Free a block of memory previously allocated from
204 * the region whose state is in the blob
205 * note: in multi thread/process, the caller needs to do a critical section
206  ********************************************************************/
207 void bmFree(void * blob, uint8_t *p, uint32_t size)
209     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) blob;
210     unsigned int off = p-pCtx->pBase;
211     int wpos, bpos;
212     int ewpos, ebpos;
213     int szinpages = size/pCtx->PSZ;
214     if (off > pCtx->maxsize) return;
215     if (szinpages*pCtx->PSZ != size) size = (szinpages+1)*pCtx->PSZ;
216     wpos= bmToWordBit(pCtx,  off, &bpos);
217     ewpos= bmToWordBit(pCtx, off+size, &ebpos);
218     //adjust by 1
219     if (ebpos==0) { ebpos=31; ewpos-=1;} else {ebpos-=1;}
220     bmSetBits(pCtx, wpos,bpos,ewpos,ebpos,0);
224 /********************************************************************
225 * FUNCTION PURPOSE: Open a bit map alloc instance on a memory region
226 ********************************************************************
227 * DESCRIPTION:  Open a bit map alloc instance on a memory area
228 *     base:      ptr to start of memory area to be managed 
229 *     max_size:  size of memory area in bytes
230 *     bitmap:    pointer to bitmap area (typically just in front of pbase)
231 *  (note: Master process needs to make sure bitmap is zeroed)
232 *     psize:     page size to use. If user, PSZ_DEF is assumed
233 * Return: a ptr to a blob holding the state of the region
234 * ********************************************************************/
235 void * bmAllocInit(uint8_t * base, uint32_t max_size, uint32_t *bitmap, uint32_t psize)
237     int l;  
238     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) malloc(sizeof(BM_MALLOC_STATE_T));
239     if (!pCtx) return (void*) NULL;
240     pCtx->maxsize = max_size;
241     pCtx->bmap = bitmap;
242     pCtx->pBase=base;
243     /* todo other checks for PSZ: ^2, >= 64, .. */
244     pCtx->PSZ = psize? psize: PSZ_DEF;
245     pCtx->NPAGES= pCtx->maxsize/pCtx->PSZ;
246     //make sure NPAGES is multiple of 32
247     l= pCtx->NPAGES/(8*sizeof(uint32_t)); 
248     if ((l * 8 * sizeof(uint32_t)) < pCtx->NPAGES)
249         pCtx->NPAGES= l*8*sizeof(uint32_t); 
250     if (pCtx->maxsize > pCtx->NPAGES*pCtx->PSZ)
251     {
252         pCtx->maxsize=pCtx->NPAGES*pCtx->PSZ;
253     }
254     return (void *) pCtx;
257 /********************************************************************
258 * FUNCTION PURPOSE: Close bit map alloc instance instance context
259 ********************************************************************
260 * DESCRIPTION:  Close bit map alloc instance instance context
261  ********************************************************************/
262 void bmAllocClose(void * blob)
264     free(blob);