5e1763397d94731cdef5ded34343ad025cd89caf
[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         for(j=0;j<(8*sizeof(uint32_t));j++)
141         {
142             if (!flag)
143             { 
144                 if (*pW & ( 1<<(31-j)) ) continue;
145                 c=1;
146                 flag= 1;
147                 wordpos = ewordpos=i;
148                 bitpos= ebitpos=j;
149             }
150             else
151             {
152                 if (c==szinpages) continue; //skipping rest of inner loop
153                 if(*pW & (1<<(31-j)) )
154                 {
155                     //not large enough
156                     c=0;
157                     flag=0;
158                     continue;
159                 }
160                 c +=1;
161                 ewordpos=i;
162                 ebitpos=j;
163             }
164         }
165         pW+=1;
166         i+=1;
167     }
168     if (c!=szinpages)
169     {
170         return -1;
171     }
172     //got it
173     bmSetBits(p,wordpos,bitpos, ewordpos, ebitpos, 1);
174     return bmOff(p,wordpos,bitpos);
180 /********************************************************************
181 * FUNCTION PURPOSE: Malloc a block of memory from memory area
182 ********************************************************************
183 * DESCRIPTION:  Malloc a block from the region whose state is in blob
184 * Note:in multi proc/multi thread, caller needs to do a critical section
185  ********************************************************************/
186 uint8_t* bmAlloc(void* blob, uint32_t size)
188     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) blob;
189     int off;
190     
191     if (size> pCtx->maxsize) return NULL;
193     off= bmFindSlots(pCtx,size);
194     if (off<0)
195         return NULL;
196      return &pCtx->pBase[off];
198 /********************************************************************
199 * FUNCTION PURPOSE: Free back  a block of memory from allocated memory 
200 *                   retion
201 ********************************************************************
202 * DESCRIPTION:  Free a block of memory previously allocated from
203 * the region whose state is in the blob
204 * note: in multi thread/process, the caller needs to do a critical section
205  ********************************************************************/
206 void bmFree(void * blob, uint8_t *p, uint32_t size)
208     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) blob;
209     unsigned int off = p-pCtx->pBase;
210     int wpos, bpos;
211     int ewpos, ebpos;
212     int szinpages = size/pCtx->PSZ;
213     if (off > pCtx->maxsize) return;
214     if (szinpages*pCtx->PSZ != size) size = (szinpages+1)*pCtx->PSZ;
215     wpos= bmToWordBit(pCtx,  off, &bpos);
216     ewpos= bmToWordBit(pCtx, off+size, &ebpos);
217     //adjust by 1
218     if (ebpos==0) { ebpos=31; ewpos-=1;} else {ebpos-=1;}
219     bmSetBits(pCtx, wpos,bpos,ewpos,ebpos,0);
223 /********************************************************************
224 * FUNCTION PURPOSE: Open a bit map alloc instance on a memory region
225 ********************************************************************
226 * DESCRIPTION:  Open a bit map alloc instance on a memory area
227 *     base:      ptr to start of memory area to be managed 
228 *     max_size:  size of memory area in bytes
229 *     bitmap:    pointer to bitmap area (typically just in front of pbase)
230 *  (note: Master process needs to make sure bitmap is zeroed)
231 *     psize:     page size to use. If user, PSZ_DEF is assumed
232 * Return: a ptr to a blob holding the state of the region
233 * ********************************************************************/
234 void * bmAllocInit(uint8_t * base, uint32_t max_size, uint32_t *bitmap, uint32_t psize)
236     int l;  
237     BM_MALLOC_STATE_T *pCtx= (BM_MALLOC_STATE_T *) malloc(sizeof(BM_MALLOC_STATE_T));
238     if (!pCtx) return (void*) NULL;
239     pCtx->maxsize = max_size;
240     pCtx->bmap = bitmap;
241     pCtx->pBase=base;
242     /* todo other checks for PSZ: ^2, >= 64, .. */
243     pCtx->PSZ = psize? psize: PSZ_DEF;
244     pCtx->NPAGES= pCtx->maxsize/pCtx->PSZ;
245     //make sure NPAGES is multiple of 32
246     l= pCtx->NPAGES/(8*sizeof(uint32_t)); 
247     if ((l * 8 * sizeof(uint32_t)) < pCtx->NPAGES)
248         pCtx->NPAGES= l*8*sizeof(uint32_t); 
249     if (pCtx->maxsize > pCtx->NPAGES*pCtx->PSZ)
250     {
251         pCtx->maxsize=pCtx->NPAGES*pCtx->PSZ;
252     }
253     return (void *) pCtx;
256 /********************************************************************
257 * FUNCTION PURPOSE: Close bit map alloc instance instance context
258 ********************************************************************
259 * DESCRIPTION:  Close bit map alloc instance instance context
260  ********************************************************************/
261 void bmAllocClose(void * blob)
263     free(blob);