?lang_form? ?lang_select? ?lang_submit? ?lang_endform?
{HEADER END}
{BLAME START}

library

?curdirlinks? -

Blame information for rev 32

Line No. Rev Author Line
1 32 kaklik /*****************************************************************************
2 *
3 * Simple SRAM Dynamic Memory Allocation
4 *
5 *****************************************************************************
6 * FileName: sralloc.c
7 * Dependencies:
8 * Processor: PIC18F with CAN
9 * Compiler: C18 02.20.00 or higher
10 * Linker: MPLINK 03.40.00 or higher
11 * Company: Microchip Technology Incorporated
12 *
13 * Software License Agreement
14 *
15 * The software supplied herewith by Microchip Technology Incorporated
16 * (the "Company") is intended and supplied to you, the Company's
17 * customer, for use solely and exclusively with products manufactured
18 * by the Company.
19 *
20 * The software is owned by the Company and/or its supplier, and is
21 * protected under applicable copyright laws. All rights are reserved.
22 * Any use in violation of the foregoing restrictions may subject the
23 * user to criminal sanctions under applicable laws, as well as to
24 * civil liability for the breach of the terms and conditions of this
25 * license.
26 *
27 * THIS SOFTWARE IS PROVIDED IN AN "AS IS" CONDITION. NO WARRANTIES,
28 * WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING, BUT NOT LIMITED
29 * TO, IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
30 * PARTICULAR PURPOSE APPLY TO THIS SOFTWARE. THE COMPANY SHALL NOT,
31 * IN ANY CIRCUMSTANCES, BE LIABLE FOR SPECIAL, INCIDENTAL OR
32 * CONSEQUENTIAL DAMAGES, FOR ANY REASON WHATSOEVER.
33 *
34 *
35 * This is a simple dynamic memory allocation module. The following are the
36 * supported services:
37 *
38 * unsigned char * NEAR SRAMalloc(NEAR unsigned char nBytes)
39 * void SRAMfree(unsigned char * NEAR pSRAM)
40 * void SRAMInitHeap(void)
41 *
42 * This version of the dynamic memory allocation limits the segment size
43 * to 126 bytes. This is specifically designed such to enable better
44 * performance by limiting pointer manipulation.
45 *
46 *
47 * How it works:
48 * The model is based on a simple form of a linked list. A block of memory
49 * refered to as the dynamic heap is split into segments. Each segment
50 * has a single byte header that references the next segment in the list
51 * as well as indicating whether the segment is allocated. Consiquently
52 * the reference implicitly identifies the length of the segment.
53 *
54 * This method also enables the possibility of allowing a large number
55 * of memory allocations. The maximum is limited by the defined heap size.
56 *
57 * SRAMalloc() is used to split or merge segments to be allocated.
58 * SRAMfree() is used to release segments.
59 *
60 * Example:
61 * ----------
62 * | 0x7F | 0x200 Header Seg1
63 * | |
64 * | |
65 * | |
66 * | |
67 * | |
68 * | |
69 * | 0x89 | 0x27F Header Seg2 (allocated)
70 * | |
71 * | |
72 * | 0x77 | 0x288 Header Seg3
73 * | |
74 * | |
75 * | |
76 * | |
77 * | |
78 * | |
79 * | |
80 * | 0x00 | 0x2FF Tail
81 * ----------
82 *
83 *
84 * Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
85 *
86 * Alloc ------------- reference to next Header --------------
87 *
88 *
89 * Recomendations:
90 * Although this model will allow dynamic allocation down to a single byte,
91 * doing so sacrifices performance. With more segments within the heap, more
92 * time is required to attempt to allocate memory. Plus every segment requires
93 * a header byte; therefore, smaller segments require more memory. There is
94 * also the possibility of fragmentation, which could ultimately doom an
95 * application by reducing the largest allocatable block of memory. Thus the
96 * recomendation is to allocate at least 8 bytes of memory.
97 *
98 *
99 *
100 * Author Date Version Comment
101 *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
102 * Ross Fosler 05/25/03 v1.03 ... First release
103 *
104 *****************************************************************************/
105  
106 // Summary: A macro used to enable nead-model RAM addressing
107 // Description: By uncommenting the NEAR_MODEL macro, the user can enable near-model RAM addressing when using dynamic FSFILE object
108 // allocation with PIC18
109 #define NEAR_MODEL
110  
111 // Summary: A macro used to define the heap size for PIC18
112 // Description: When using dynamic FSFILE object allocation with PIC18, the MAX_HEAP_SIZE will allow the user to specify the size
113 // of the dynamic heap to use
114 #define MAX_HEAP_SIZE 0x100
115  
116  
117  
118 #if defined(NEAR_MODEL)
119 // Summary: A macro used to specify the near-model action
120 // Description: Functions can be declared using the NEAR macro. If the NEAR_MODEL macro is uncommented, the NEAR macro will be ignored.
121 #define NEAR near
122 #else
123 #define NEAR
124 #endif
125  
126 // Description: A macro used to determine the maximum size of a dynamic memory segment.
127 #define _MAX_SEGMENT_SIZE 0x7F
128 // Description: A macro used to determine the heap initialization size.
129 #define _MAX_HEAP_SIZE MAX_HEAP_SIZE-1
130  
131  
132  
133 // Summary: The segment header data type
134 // Description: The SALLOC union allows the PIC18 dynamic memory allocation algorithm to perform bitwise accesses on segment headers.
135 typedef union _SALLOC
136 {
137 unsigned char byte;
138 struct _BITS
139 {
140 unsigned count:7;
141 unsigned alloc:1;
142 }bits;
143 }SALLOC;
144  
145  
146  
147  
148  
149 /*********************************************************************
150 * Reserve the memory heap
151 ********************************************************************/
152 #pragma udata _SRAM_ALLOC_HEAP
153 // Summary: The PIC18 dynamic memory heap
154 // Description: The _uDynamicHeap array is used as a heap for PIC18 dynamic memory allocation.
155 unsigned char _uDynamicHeap[MAX_HEAP_SIZE];
156  
157  
158 /*********************************************************************
159 * Set the memory type
160 ********************************************************************/
161 #if defined(NEAR_MODEL)
162 #pragma udata access _SRAM_ALLOC
163 #else
164 #pragma udata _SRAM_ALLOC
165 #endif
166  
167  
168  
169 /*********************************************************************
170 * Private function declarations
171 ********************************************************************/
172 NEAR unsigned char _SRAMmerge(SALLOC * NEAR pSegA);
173  
174  
175  
176  
177 /*********************************************************************
178 * Function: unsigned char * SRAMalloc(unsigned char length)
179 *
180 * PreCondition: A memory block must be allocated in the linker,
181 * and the memory headers and tail must already be
182 * set via the function SRAMInitHeap().
183 *
184 * Input: unsigned char nBytes - Number of bytes to allocate.
185 *
186 * Output: unsigned char * - A pointer to the requested block
187 * of memory.
188 *
189 * Side Effects:
190 *
191 * Overview: This functions allocates a chunk of memory from
192 * the heap. The maximum segment size for this
193 * version is 126 bytes. If the heap does not have
194 * an available segment of sufficient size it will
195 * attempt to create a segment; otherwise a NULL
196 * pointer is returned. If allocation is succeessful
197 * then a pointer to the requested block is returned.
198 *
199 * Note: The calling function must maintain the pointer
200 * to correctly free memory at runtime.
201 ********************************************************************/
202 unsigned char * NEAR SRAMalloc(NEAR unsigned char nBytes)
203 {
204 SALLOC * NEAR pHeap;
205 SALLOC * NEAR temp;
206 NEAR SALLOC segHeader;
207 NEAR unsigned char segLen;
208  
209 // Do not allow allocation above the max minus one bytes
210 if (nBytes > (_MAX_SEGMENT_SIZE - 1)) return (0);
211  
212 // Init the pointer to the heap
213 pHeap = (SALLOC *)_uDynamicHeap;
214  
215 while (1)
216 {
217 // Get the header of the segment
218 segHeader = *pHeap;
219  
220 // Extract the segment length from the segment
221 segLen = segHeader.bits.count - 1;
222  
223 // A null segment indicates the end of the table
224 if (segHeader.byte == 0) return (0);
225  
226 // If this segment is not allocated then attempt to allocate it
227 if (!(segHeader.bits.alloc))
228 {
229 // If the free segment is too small then attempt to merge
230 if (nBytes > segLen)
231 {
232 // If the merge fails them move on to the next segment
233 if (!(_SRAMmerge(pHeap))) pHeap += segHeader.bits.count;
234 }
235 else
236  
237 // If the segment length matches the request then allocate the
238 // header and return the pointer
239 if (nBytes == segLen)
240 {
241 // Allocate the segment
242 (*pHeap).bits.alloc = 1;
243  
244 // Return the pointer to the caller
245 return ((unsigned char *)(pHeap + 1));
246 }
247  
248 // Else create a new segment
249 else
250 {
251 // Reset the header to point to a new segment
252 (*pHeap).byte = nBytes + 0x81;
253  
254 // Remember the pointer to the first segment
255 temp = pHeap + 1;
256  
257 // Point to the new segment
258 pHeap += (nBytes + 1);
259  
260 // Insert the header for the new segment
261 (*pHeap).byte = segLen - nBytes;
262  
263 // Return the pointer to the user
264 return ((unsigned char *) temp);
265 }
266 }
267  
268 // else set the pointer to the next segment header in the heap
269 else
270 {
271 pHeap += segHeader.bits.count;
272 }
273 }
274 }
275  
276  
277  
278 /*********************************************************************
279 * Function: void SRAMfree(unsigned char * pSRAM)
280 *
281 * PreCondition: The pointer must have been returned from a
282 * previously allocation via SRAMalloc().
283 *
284 * Input: unsigned char * pSRAM - pointer to the allocated
285 *
286 * Output: void
287 *
288 * Side Effects:
289 *
290 * Overview: This function de-allocates a previously allocated
291 * segment of memory.
292 *
293 * Note: The pointer must be a valid pointer returned from
294 * SRAMalloc(); otherwise, the segment may not be
295 * successfully de-allocated, and the heap may be
296 * corrupted.
297 ********************************************************************/
298 void SRAMfree(unsigned char * NEAR pSRAM)
299 {
300 // Release the segment
301 (*(SALLOC *)(pSRAM - 1)).bits.alloc = 0;
302 }
303  
304  
305  
306 /*********************************************************************
307 * Function: void SRAMInitHeap(void)
308 *
309 * PreCondition:
310 *
311 * Input: void
312 *
313 * Output: void
314 *
315 * Side Effects:
316 *
317 * Overview: This function initializes the dynamic heap. It
318 * inserts segment headers to maximize segment space.
319 *
320 * Note: This function must be called at least one time.
321 * And it could be called more times to reset the
322 * heap.
323 ********************************************************************/
324 void SRAMInitHeap(void)
325 {
326 unsigned char * NEAR pHeap;
327 NEAR unsigned int count;
328  
329 pHeap = _uDynamicHeap;
330 count = _MAX_HEAP_SIZE;
331  
332 while (1)
333 {
334 if (count > _MAX_SEGMENT_SIZE)
335 {
336 *pHeap = _MAX_SEGMENT_SIZE;
337 pHeap += _MAX_SEGMENT_SIZE;
338 count = count - _MAX_SEGMENT_SIZE;
339 }
340 else
341 {
342 *pHeap = count;
343 *(pHeap + count) = 0;
344 return;
345 }
346 }
347 }
348  
349  
350  
351  
352 /*********************************************************************
353 * Function: unsigned char _SRAMmerge(SALLOC * NEAR pSegA)
354 *
355 * PreCondition:
356 *
357 * Input: SALLOC * NEAR pSegA - pointer to the first segment.
358 *
359 * Output: usnigned char - returns the length of the
360 * merged segment or zero if failed to merge.
361 *
362 * Side Effects:
363 *
364 * Overview: This function tries to merge adjacent segments
365 * that have not been allocated. The largest possible
366 * segment is merged if possible.
367 *
368 * Note:
369 ********************************************************************/
370 NEAR unsigned char _SRAMmerge(SALLOC * NEAR pSegA)
371 {
372 SALLOC * NEAR pSegB;
373 NEAR SALLOC uSegA, uSegB, uSum;
374  
375  
376 // Init the pointer to the heap
377 pSegB = pSegA + (*pSegA).byte;
378  
379 // Extract the headers for faster processing
380 uSegA = *pSegA;
381 uSegB = *pSegB;
382  
383 // Quit if the tail has been found
384 if (uSegB.byte == 0) return (0);
385  
386 // If either segment is allocated then do not merge
387 if (uSegA.bits.alloc || uSegB.bits.alloc) return (0);
388  
389 // If the first segment is max then nothing to merge
390 if (uSegA.bits.count == _MAX_SEGMENT_SIZE) return (0);
391  
392 // Get the sum of the two segments
393 uSum.byte = uSegA.byte + uSegB.byte;
394  
395  
396 // If the sum of the two segments are > than the largest segment
397 // then create a new segment equal to the max segment size and
398 // point to the next segments
399 if ((uSum.byte) > _MAX_SEGMENT_SIZE)
400 {
401 (*pSegA).byte = _MAX_SEGMENT_SIZE;
402 pSegA += _MAX_SEGMENT_SIZE; //(*pSeg1).byte;
403 pSegB += uSegB.byte; //(*pSeg2).byte ;
404 (*pSegA).byte = pSegB - pSegA;
405  
406 return (_MAX_SEGMENT_SIZE);
407 }
408 // Else combine the two segments into one segment and
409 // do not adjust the pointers to the next segment
410 else
411 {
412 return ((*pSegA).byte = uSum.byte);
413 }
414 }
415  
416  
417  
{BLAME END}
{FOOTER START}

Powered by WebSVN v2.8.3