|
1 // Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of the License "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // |
|
15 |
|
16 #include <plat_priv.h> |
|
17 #include "mm.h" |
|
18 #include "mmu.h" |
|
19 #include "mvalloc.h" |
|
20 #include "maddrcont.h" |
|
21 |
|
22 |
|
23 /** |
|
24 Log2 of the minimum granularity and alignment of virtual address allocation. |
|
25 Must be greater than or equal to #KPageShift+#KPageColourShift. |
|
26 */ |
|
27 const TUint KVirtualAllocShift = KPageShift+KPageColourShift; |
|
28 |
|
29 /** |
|
30 Log2 of the size of the region covered by a single 'slab' of virtual addresses. |
|
31 Must be greater than or equal to KChunkShift. |
|
32 */ |
|
33 const TUint KVirtualAllocSlabShift = KChunkShift; |
|
34 |
|
35 /** |
|
36 Size, in bytes, of the size of the region covered by a single 'slab' of virtual addresses. |
|
37 */ |
|
38 const TUint KVirtualAllocSlabSize = 1<<KVirtualAllocSlabShift; |
|
39 |
|
40 const TUint KVirtualAllocSlabMask = KVirtualAllocSlabSize-1; |
|
41 |
|
42 __ASSERT_COMPILE(KVirtualAllocShift>=KPageShift+KPageColourShift); |
|
43 __ASSERT_COMPILE(KVirtualAllocSlabShift>=TUint(KChunkShift)); |
|
44 |
|
45 |
|
46 #if defined(__GCCXML__) |
|
47 FORCE_INLINE TUint CountLeadingZeroes(TUint32 /*aValue*/) |
|
48 { |
|
49 // empty |
|
50 return 0; |
|
51 } |
|
52 |
|
53 #elif defined(__MARM__) |
|
54 |
|
55 #ifdef __ARMCC__ |
|
56 FORCE_INLINE TUint CountLeadingZeroes(TUint32 aValue) |
|
57 { |
|
58 #if __ARMCC_VERSION < 310000 |
|
59 TUint r; |
|
60 asm("clz r,aValue"); |
|
61 return r; |
|
62 #else |
|
63 // Inline assembler is deprecated in RVCT 3.1 so we use an intrinsic. |
|
64 return __clz(aValue); |
|
65 #endif |
|
66 } |
|
67 #endif // __ARMCC__ |
|
68 |
|
69 #ifdef __MARM_ARM4__ |
|
70 __declspec(naked) static TUint CountLeadingZeroes(TUint32) |
|
71 { |
|
72 CLZ(0,0); |
|
73 __JUMP(,lr); |
|
74 } |
|
75 |
|
76 #elif defined(__GNUC__) |
|
77 FORCE_INLINE TUint CountLeadingZeroes(TUint32 aValue) |
|
78 { |
|
79 TUint r; |
|
80 asm("clz %0,%1" : "=r"(r) : "r"(aValue)); |
|
81 return r; |
|
82 } |
|
83 #endif // __GNUC__ |
|
84 |
|
85 #else // !__MARM__ |
|
86 |
|
87 inline TUint CountLeadingZeroes(TUint32 aValue) |
|
88 { |
|
89 if(!aValue) |
|
90 return 32; |
|
91 TUint count = 31; |
|
92 if(aValue>=(1<<16)) |
|
93 { |
|
94 count -= 16; |
|
95 aValue >>= 16; |
|
96 } |
|
97 if(aValue>=(1<<8)) |
|
98 { |
|
99 count -= 8; |
|
100 aValue >>= 8; |
|
101 } |
|
102 if(aValue>=(1<<4)) |
|
103 { |
|
104 count -= 4; |
|
105 aValue >>= 4; |
|
106 } |
|
107 if(aValue>=(1<<2)) |
|
108 { |
|
109 count -= 2; |
|
110 aValue >>= 2; |
|
111 } |
|
112 count -= aValue>>1; |
|
113 return count; |
|
114 } |
|
115 |
|
116 #endif // __MARM__ |
|
117 |
|
118 |
|
119 |
|
120 // |
|
121 // TLogAllocator |
|
122 // |
|
123 |
|
124 /** |
|
125 Bitmap allocator for allocating regions which have size and alignment which |
|
126 are a power-of-two. |
|
127 */ |
|
128 class TLogAllocator |
|
129 { |
|
130 public: |
|
131 TLogAllocator(); |
|
132 |
|
133 /** |
|
134 Find and allocate a free region in the bitmap. |
|
135 |
|
136 @param aSizeShift Log2 of the number of bits to allocate. |
|
137 |
|
138 @return If successful, the index of the first bit allocated. |
|
139 Otherwise, -1. |
|
140 */ |
|
141 TInt Alloc(TUint aSizeShift); |
|
142 |
|
143 /** |
|
144 Allocate a specific region of bits. |
|
145 |
|
146 @param aIndex The index of the first bit to allocated. |
|
147 Must be a integer multiple of 2^aSizeShift. |
|
148 @param aSizeShift Log2 of the number of bits to allocate. |
|
149 |
|
150 @return KErrNone, if successful; |
|
151 KErrAlreadyExists, if any part of the region was already allocated. |
|
152 */ |
|
153 TInt Alloc(TUint aIndex, TUint aSizeShift); |
|
154 |
|
155 /** |
|
156 Free a specific region of bits. |
|
157 |
|
158 @param aIndex The index of the first bit to free. |
|
159 Must be a integer multiple of 2^aSizeShift. |
|
160 |
|
161 @param aSizeShift Log2 of the number of bits to free. |
|
162 |
|
163 @return True, if the slab no longer has any bits allocated. |
|
164 */ |
|
165 TBool Free(TUint aIndex, TUint aSizeShift); |
|
166 private: |
|
167 enum |
|
168 { |
|
169 ENumBits = 1<<(KVirtualAllocSlabShift-KVirtualAllocShift), |
|
170 ENumWords = (ENumBits+31)/32 |
|
171 }; |
|
172 |
|
173 /** |
|
174 Number of bits which have been allocated. |
|
175 */ |
|
176 TUint iAllocCount; |
|
177 |
|
178 /** |
|
179 Bitmap where a bit set to one indicates 'free' and a bit cleared to zero |
|
180 indicates 'allocated'. The most significant bit in each word has the lowest |
|
181 index value. E.g. |
|
182 - Index 0 is bit 31 of iBits[0] |
|
183 - Index 31 is bit 0 of iBits[0] |
|
184 - Index 32 is bit 31 of iBits[1] |
|
185 */ |
|
186 TUint32 iBits[ENumWords]; |
|
187 }; |
|
188 |
|
189 |
|
190 TLogAllocator::TLogAllocator() |
|
191 { |
|
192 iAllocCount = 0; |
|
193 memset(iBits,~0u,sizeof(iBits)); // unallocated bits are set to one |
|
194 } |
|
195 |
|
196 |
|
197 TInt TLogAllocator::Alloc(TUint aSizeShift) |
|
198 { |
|
199 TUint size = 1<<aSizeShift; |
|
200 |
|
201 __NK_ASSERT_DEBUG(size<=ENumBits); // check in range |
|
202 |
|
203 TUint32* bits = iBits; |
|
204 TUint32* bitsEnd = bits+ENumWords; |
|
205 TUint32 b; |
|
206 switch(aSizeShift) |
|
207 { |
|
208 case 0: // find word with any unallocated bits... |
|
209 do |
|
210 { |
|
211 b = *bits++; |
|
212 if(b) |
|
213 goto small_found; |
|
214 } |
|
215 while(bits<bitsEnd); |
|
216 break; |
|
217 |
|
218 case 1: // find word with 2 adjacent unallocated bits... |
|
219 do |
|
220 { |
|
221 b = *bits++; |
|
222 b &= b<<1; |
|
223 b &= 0xaaaaaaaa; |
|
224 if(b) |
|
225 goto small_found; |
|
226 } |
|
227 while(bits<bitsEnd); |
|
228 break; |
|
229 |
|
230 case 2: // find word with 4 adjacent unallocated bits... |
|
231 do |
|
232 { |
|
233 b = *bits++; |
|
234 b &= b<<1; |
|
235 b &= b<<2; |
|
236 b &= 0x88888888; |
|
237 if(b) |
|
238 goto small_found; |
|
239 } |
|
240 while(bits<bitsEnd); |
|
241 break; |
|
242 |
|
243 case 3: // find word with 8 adjacent unallocated bits... |
|
244 do |
|
245 { |
|
246 b = *bits++; |
|
247 b &= b<<1; |
|
248 b &= b<<2; |
|
249 b &= b<<4; |
|
250 b &= 0x80808080; |
|
251 if(b) |
|
252 goto small_found; |
|
253 } |
|
254 while(bits<bitsEnd); |
|
255 break; |
|
256 |
|
257 case 4: // find word with 16 adjacent unallocated bits... |
|
258 do |
|
259 { |
|
260 b = *bits++; |
|
261 b &= b<<1; |
|
262 b &= b<<2; |
|
263 b &= b<<4; |
|
264 b &= b<<8; |
|
265 b &= 0x80008000; |
|
266 if(b) |
|
267 goto small_found; |
|
268 } |
|
269 while(bits<bitsEnd); |
|
270 break; |
|
271 |
|
272 case 5: // find word which is totally unallocated (has 32 bits free)... |
|
273 do |
|
274 { |
|
275 b = *bits++; |
|
276 if(b==0xffffffffu) |
|
277 goto big_found; |
|
278 } |
|
279 while(bits<bitsEnd); |
|
280 break; |
|
281 |
|
282 default: // find relevant number of words which are unallocated... |
|
283 { |
|
284 do |
|
285 { |
|
286 // AND words together... |
|
287 TUint32* end = (TUint32*)((TUint8*)bits+(size>>3)); |
|
288 TUint32 b = 0xffffffffu; |
|
289 do b &= *bits++; |
|
290 while(bits<end); |
|
291 |
|
292 if(b==0xffffffffu) |
|
293 goto big_found; // all were free |
|
294 } |
|
295 while(bits<bitsEnd); |
|
296 break; |
|
297 } |
|
298 |
|
299 } |
|
300 __NK_ASSERT_DEBUG(bits==bitsEnd); |
|
301 return -1; |
|
302 |
|
303 small_found: |
|
304 { |
|
305 // find first position in word which have free region (a bit set to one)... |
|
306 TUint offset = CountLeadingZeroes(b); |
|
307 |
|
308 // clear bits... |
|
309 TUint32 mask = 0xffffffffu; |
|
310 mask >>= size; |
|
311 mask = ~mask; |
|
312 mask >>= offset; |
|
313 *--bits &= ~mask; |
|
314 |
|
315 // calculate index for allocated region... |
|
316 TUint index = (bits-iBits)*32+offset; |
|
317 |
|
318 iAllocCount += size; |
|
319 return index; |
|
320 } |
|
321 |
|
322 big_found: |
|
323 { |
|
324 // clear bits... |
|
325 TUint32* start = (TUint32*)((TUint8*)bits-(size>>3)); |
|
326 do *--bits = 0; |
|
327 while(bits>start); |
|
328 |
|
329 // calculate index for allocated region... |
|
330 TUint index = (bits-iBits)*32; |
|
331 |
|
332 iAllocCount += size; |
|
333 return index; |
|
334 } |
|
335 |
|
336 } |
|
337 |
|
338 |
|
339 TInt TLogAllocator::Alloc(TUint aIndex, TUint aSizeShift) |
|
340 { |
|
341 TUint size = 1<<aSizeShift; |
|
342 |
|
343 __NK_ASSERT_DEBUG(aIndex+size>aIndex); // check overflow |
|
344 __NK_ASSERT_DEBUG(aIndex+size<=ENumBits); // check in range |
|
345 __NK_ASSERT_DEBUG(((aIndex>>aSizeShift)<<aSizeShift)==aIndex); // check alignment |
|
346 |
|
347 TUint32* bits = iBits+(aIndex>>5); |
|
348 if(size<32) |
|
349 { |
|
350 TUint32 mask = 0xffffffffu; |
|
351 mask >>= size; |
|
352 mask = ~mask; |
|
353 mask >>= aIndex&31; |
|
354 TUint32 b = *bits; |
|
355 if((b&mask)!=mask) |
|
356 return KErrAlreadyExists; |
|
357 *bits = b&~mask; |
|
358 } |
|
359 else |
|
360 { |
|
361 TUint32* start = bits; |
|
362 TUint32* end = bits+(size>>5); |
|
363 do if(*bits++!=0xffffffffu) return KErrAlreadyExists; |
|
364 while(bits<end); |
|
365 |
|
366 bits = start; |
|
367 do *bits++ = 0; |
|
368 while(bits<end); |
|
369 } |
|
370 |
|
371 iAllocCount += size; |
|
372 return KErrNone; |
|
373 } |
|
374 |
|
375 |
|
376 TBool TLogAllocator::Free(TUint aIndex, TUint aSizeShift) |
|
377 { |
|
378 TUint size = 1<<aSizeShift; |
|
379 |
|
380 __NK_ASSERT_DEBUG(aIndex+size>aIndex); // check overflow |
|
381 __NK_ASSERT_DEBUG(aIndex+size<=ENumBits); // check in range |
|
382 __NK_ASSERT_DEBUG(((aIndex>>aSizeShift)<<aSizeShift)==aIndex); // check alignment |
|
383 |
|
384 TUint32* bits = iBits+(aIndex>>5); |
|
385 if(size<32) |
|
386 { |
|
387 TUint32 mask = 0xffffffffu; |
|
388 mask >>= size; |
|
389 mask = ~mask; |
|
390 mask >>= aIndex&31; |
|
391 TUint32 b = *bits; |
|
392 __NK_ASSERT_DEBUG((b&mask)==0); // check was allocated |
|
393 *bits = b|mask; |
|
394 } |
|
395 else |
|
396 { |
|
397 TUint wordCount = size>>5; |
|
398 do |
|
399 { |
|
400 __NK_ASSERT_DEBUG(bits[0]==0); |
|
401 *bits++ = 0xffffffffu; |
|
402 } |
|
403 while(--wordCount); |
|
404 } |
|
405 |
|
406 iAllocCount -= size; |
|
407 return !iAllocCount; |
|
408 } |
|
409 |
|
410 |
|
411 |
|
412 // |
|
413 // TVirtualSlab |
|
414 // |
|
415 |
|
416 /** |
|
417 Class for allocating virtual addresses contained in a single 'slab'. |
|
418 @see RVirtualAllocSlabSet. |
|
419 */ |
|
420 class TVirtualSlab |
|
421 { |
|
422 public: |
|
423 /** |
|
424 @param aHead The head of a linked list of slabs to which this one should be added. |
|
425 @param aBase The starting virtual address of the region covered by this slab. |
|
426 @param aSlabType The 'slab type'. |
|
427 */ |
|
428 TVirtualSlab(SDblQue& aHead, TUint aBase, TUint aSlabType); |
|
429 |
|
430 ~TVirtualSlab(); |
|
431 |
|
432 /** |
|
433 Find an allocate a free region of virtual addresses. |
|
434 |
|
435 @param aSizeShift Log2 of the size, in bytes, of the region. |
|
436 |
|
437 @return If successful, the allocated virtual address. |
|
438 Otherwise, 0 (zero). |
|
439 */ |
|
440 TLinAddr Alloc(TUint aSizeShift); |
|
441 |
|
442 /** |
|
443 Allocate a specific region of virtual addresses. |
|
444 |
|
445 @param aAddr The start address of the region. |
|
446 Must be a integer multiple of 2^aSizeShift. |
|
447 @param aSizeShift Log2 of the size, in bytes, of the region. |
|
448 |
|
449 |
|
450 @return KErrNone, if successful; |
|
451 KErrAlreadyExists, if any part of the region was already allocated. |
|
452 */ |
|
453 TInt Alloc(TLinAddr aAddr, TUint aSizeShift); |
|
454 |
|
455 /** |
|
456 Free a specific region of virtual addresses. |
|
457 |
|
458 @param aAddr The start address of the region. |
|
459 Must be a integer multiple of 2^aSizeShift. |
|
460 @param aSizeShift Log2 of the size, in bytes, of the region. |
|
461 |
|
462 @return True, if the slab no longer has any addresses allocated. |
|
463 */ |
|
464 TBool Free(TLinAddr aAddr, TUint aSizeShift); |
|
465 |
|
466 /** |
|
467 Return the starting virtual address of the region covered by this slab. |
|
468 */ |
|
469 FORCE_INLINE TLinAddr Base() { return iBase; } |
|
470 |
|
471 /** |
|
472 Return this objects 'slab type'. |
|
473 */ |
|
474 FORCE_INLINE TUint SlabType() { return iSlabType; } |
|
475 private: |
|
476 /** |
|
477 Link object used to insert this slab into lists. |
|
478 */ |
|
479 SDblQueLink iLink; |
|
480 |
|
481 /** |
|
482 The starting virtual address of the region covered by this slab. |
|
483 */ |
|
484 TLinAddr iBase; |
|
485 |
|
486 /** |
|
487 This objects 'slab type'. |
|
488 */ |
|
489 TUint8 iSlabType; |
|
490 |
|
491 /** |
|
492 Bitmap allocator used to allocated pages in this slab's virtual address region. |
|
493 */ |
|
494 TLogAllocator iAllocator; |
|
495 |
|
496 friend class RVirtualAllocSlabSet; |
|
497 }; |
|
498 |
|
499 |
|
500 TVirtualSlab::TVirtualSlab(SDblQue& aHead, TUint aBase, TUint aSlabType) |
|
501 : iBase(aBase),iSlabType(aSlabType) |
|
502 { |
|
503 TRACE2(("TVirtualSlab::TVirtualSlab(?,0x%08x,%d)",aBase, aSlabType)); |
|
504 aHead.Add(&iLink); |
|
505 } |
|
506 |
|
507 |
|
508 TVirtualSlab::~TVirtualSlab() |
|
509 { |
|
510 TRACE2(("TVirtualSlab::~TVirtualSlab base=0x%08x",iBase)); |
|
511 iLink.Deque(); |
|
512 } |
|
513 |
|
514 |
|
515 TLinAddr TVirtualSlab::Alloc(TUint aSizeShift) |
|
516 { |
|
517 TRACE2(("TVirtualSlab::Alloc(%d)",aSizeShift)); |
|
518 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift); |
|
519 aSizeShift -= KVirtualAllocShift; |
|
520 TInt index = iAllocator.Alloc(aSizeShift); |
|
521 TLinAddr addr = 0; |
|
522 if(index>=0) |
|
523 addr = iBase+(index<<KVirtualAllocShift); |
|
524 TRACE2(("TVirtualSlab::Alloc returns 0x%08x",addr)); |
|
525 return addr; |
|
526 } |
|
527 |
|
528 |
|
529 TInt TVirtualSlab::Alloc(TLinAddr aAddr, TUint aSizeShift) |
|
530 { |
|
531 TRACE2(("TVirtualSlab::Alloc(0x%08x,%d)",aAddr,aSizeShift)); |
|
532 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift); |
|
533 aSizeShift -= KVirtualAllocShift; |
|
534 TUint index = (aAddr-iBase)>>KVirtualAllocShift; |
|
535 __NK_ASSERT_DEBUG(iBase+(index<<KVirtualAllocShift)==aAddr); |
|
536 TInt r = iAllocator.Alloc(index,aSizeShift); |
|
537 if(r<0) |
|
538 return r; |
|
539 TRACE2(("TVirtualSlab::Alloc returns 0x%08x",iBase+(r<<KVirtualAllocShift))); |
|
540 return r; |
|
541 } |
|
542 |
|
543 |
|
544 TBool TVirtualSlab::Free(TLinAddr aAddr, TUint aSizeShift) |
|
545 { |
|
546 TRACE2(("TVirtualSlab::Free(0x%08x,%d)",aAddr,aSizeShift)); |
|
547 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift); |
|
548 aSizeShift -= KVirtualAllocShift; |
|
549 TUint offset = aAddr-iBase; |
|
550 TUint index = offset>>KVirtualAllocShift; |
|
551 __NK_ASSERT_DEBUG((index<<KVirtualAllocShift)==offset); |
|
552 return iAllocator.Free(index,aSizeShift); |
|
553 } |
|
554 |
|
555 |
|
556 // |
|
557 // RVirtualAllocSet |
|
558 // |
|
559 |
|
560 |
|
561 /** |
|
562 Class used by #RVirtualAllocator for allocating virtual addresses which |
|
563 have a size less than a 'chunk' (#KChunkSize). |
|
564 |
|
565 This consists of a set of #TVirtualSlab objects. |
|
566 */ |
|
567 class RVirtualAllocSlabSet |
|
568 { |
|
569 public: |
|
570 /** |
|
571 Create a new slab set for use with the specified allocator. |
|
572 |
|
573 @param aAllocator The virtual address allocator which will use the slab set. |
|
574 @param aNumSlabTypes The number of slab types this allocator will support. |
|
575 @param aWriteLock Reference to the mutex which is being used to protect allocations |
|
576 with this object. This is only used for debug checks and may be |
|
577 a mutex assigned by #DMutexPool. In practice, this will usually be an |
|
578 address space lock DAddressSpace::iLock. |
|
579 |
|
580 @return The newly created #RVirtualAllocSlabSet or the null pointer if there was |
|
581 insufficient memory. |
|
582 */ |
|
583 static RVirtualAllocSlabSet* New(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock); |
|
584 |
|
585 ~RVirtualAllocSlabSet(); |
|
586 |
|
587 /** |
|
588 Allocate a region of virtual addresses. |
|
589 |
|
590 @param[in,out] aAddr On entry, if this is non-zero it represents |
|
591 the start address a specific region to allocate. |
|
592 On exit, this is set to the start address of the region allocated. |
|
593 @param aSizeShift Log2 of the size, in bytes, of the region. |
|
594 @param aSlabType The 'slab type' of the address to be allocated. |
|
595 |
|
596 @return KErrNone, if successful; |
|
597 KErrAlreadyExists, if any part of the region was already allocated. |
|
598 |
|
599 @pre The write lock must be held. (The \a aWriteLock argument for the constructor |
|
600 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.) |
|
601 */ |
|
602 TInt Alloc(TLinAddr& aAddr, TUint aSizeShift, TUint aSlabType); |
|
603 |
|
604 /** |
|
605 Free a region of virtual addresses. |
|
606 |
|
607 @param aAddr The start address of the region. |
|
608 @param aSizeShift Log2 of the size, in bytes, of the region. |
|
609 |
|
610 @pre The write lock must be held. (The \a aWriteLock argument for the constructor |
|
611 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.) |
|
612 */ |
|
613 void Free(TLinAddr aAddr, TUint aSizeShift); |
|
614 |
|
615 /** |
|
616 Return true if the the address region specified by \a aAddr and \a aSizeShift was |
|
617 allocated by this allocator using the specified \a aSlabType. |
|
618 |
|
619 @pre The write lock must be held. (The \a aWriteLock argument for the constructor |
|
620 #RVirtualAllocSlabSet::RVirtualAllocSlabSet.) |
|
621 */ |
|
622 TBool CheckSlabType(TLinAddr aAddr, TUint aSizeShift, TUint aSlabType); |
|
623 |
|
624 private: |
|
625 /** |
|
626 Create a new slab (#TVirtualSlab) for use by this slab set. |
|
627 Newly allocated slabs are added to #iLists[\a aSlabType]. |
|
628 |
|
629 The virtual address range used by the slab is obtained by |
|
630 by allocating a slab sized region from #iAllocator. |
|
631 |
|
632 @param aAddr A virtual address which must be in the region to be covered by the slab. |
|
633 @param aSlabType The 'slab type'. |
|
634 */ |
|
635 TVirtualSlab* NewSlab(TLinAddr aAddr, TUint aSlabType); |
|
636 |
|
637 /** |
|
638 Delete a slab created with #NewSlab. |
|
639 */ |
|
640 void DeleteSlab(TVirtualSlab* aSlab); |
|
641 |
|
642 /** |
|
643 Constructor, for arguments see #New. |
|
644 */ |
|
645 RVirtualAllocSlabSet(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock); |
|
646 |
|
647 private: |
|
648 /** |
|
649 The virtual allocator which is using this slab set. |
|
650 */ |
|
651 RVirtualAllocator* iAllocator; |
|
652 |
|
653 /** |
|
654 Container for all slabs owned by this slab set. This is keyed on the starting |
|
655 virtual address of the region each slab covers. |
|
656 |
|
657 Each slab in this container is also linked into the #iLists member appropriate |
|
658 to its slab type.. |
|
659 */ |
|
660 RAddressedContainer iSlabs; |
|
661 |
|
662 /** |
|
663 The number of different 'slab types' this object can allocate addresses for. |
|
664 */ |
|
665 TUint iNumSlabTypes; |
|
666 |
|
667 /** |
|
668 An array of lists which each contain slabs of a single 'slab type' |
|
669 which this object has created. Slabs are linked by their TVirtualSlab::iLink |
|
670 member. |
|
671 |
|
672 This may extend into memory beyond the end of this object and contains |
|
673 #iNumSlabTypes entries. |
|
674 |
|
675 Each slab in these lists is also contained in #iSlabs. |
|
676 */ |
|
677 SDblQue iLists[1]; |
|
678 }; |
|
679 |
|
680 |
|
681 FORCE_INLINE RVirtualAllocSlabSet::RVirtualAllocSlabSet(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock) |
|
682 : iAllocator(aAllocator), iSlabs(0,aWriteLock), iNumSlabTypes(aNumSlabTypes) |
|
683 { |
|
684 while(aNumSlabTypes--) |
|
685 new (&iLists+aNumSlabTypes) SDblQue; |
|
686 } |
|
687 |
|
688 |
|
689 RVirtualAllocSlabSet* RVirtualAllocSlabSet::New(RVirtualAllocator* aAllocator, TUint aNumSlabTypes, DMutex*& aWriteLock) |
|
690 { |
|
691 TUint size = sizeof(RVirtualAllocSlabSet)+sizeof(((RVirtualAllocSlabSet*)0x100)->iSlabs)*(aNumSlabTypes-1); |
|
692 RVirtualAllocSlabSet* set = (RVirtualAllocSlabSet*)Kern::AllocZ(size); |
|
693 if(set) |
|
694 new (set) RVirtualAllocSlabSet(aAllocator,aNumSlabTypes,aWriteLock); |
|
695 return set; |
|
696 } |
|
697 |
|
698 |
|
699 RVirtualAllocSlabSet::~RVirtualAllocSlabSet() |
|
700 { |
|
701 __NK_ASSERT_DEBUG(iSlabs.Count()==0); |
|
702 } |
|
703 |
|
704 |
|
705 TVirtualSlab* RVirtualAllocSlabSet::NewSlab(TLinAddr aAddr, TUint aSlabType) |
|
706 { |
|
707 TRACE2(("RVirtualAllocSlabSet::NewSlab(0x%08x,%d,%d)",aAddr,aSlabType)); |
|
708 __NK_ASSERT_DEBUG(aSlabType<iNumSlabTypes); |
|
709 |
|
710 TVirtualSlab* slab = 0; |
|
711 TLinAddr base; |
|
712 TUint size; |
|
713 TInt r = iAllocator->Alloc(base,size,aAddr&~KVirtualAllocSlabMask,KVirtualAllocSlabSize,aSlabType); |
|
714 if(r==KErrNone) |
|
715 { |
|
716 slab = new TVirtualSlab(iLists[aSlabType],base,aSlabType); |
|
717 if(slab && iSlabs.Add(base,slab)!=KErrNone) |
|
718 { |
|
719 delete slab; |
|
720 slab = 0; |
|
721 } |
|
722 if(!slab) |
|
723 iAllocator->Free(base,KVirtualAllocSlabSize); |
|
724 } |
|
725 |
|
726 TRACE2(("RVirtualAllocSlabSet::NewSlab returns 0x%08x",slab)); |
|
727 return slab; |
|
728 } |
|
729 |
|
730 |
|
731 void RVirtualAllocSlabSet::DeleteSlab(TVirtualSlab* aSlab) |
|
732 { |
|
733 TLinAddr base = aSlab->Base(); |
|
734 #ifdef _DEBUG |
|
735 TAny* removedSlab = |
|
736 #endif |
|
737 iSlabs.Remove(base); |
|
738 __NK_ASSERT_DEBUG(removedSlab==aSlab); |
|
739 delete aSlab; |
|
740 iAllocator->Free(base,KVirtualAllocSlabSize); |
|
741 } |
|
742 |
|
743 |
|
744 TInt RVirtualAllocSlabSet::Alloc(TLinAddr& aAddr, TUint aSizeShift, TUint aSlabType) |
|
745 { |
|
746 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift); |
|
747 __NK_ASSERT_DEBUG(aSlabType<iNumSlabTypes); |
|
748 |
|
749 if(!aAddr) |
|
750 { |
|
751 SDblQueLink* head = &iLists[aSlabType].iA; |
|
752 SDblQueLink* link = head; |
|
753 while((link=link->iNext)!=head) |
|
754 { |
|
755 TVirtualSlab* slab = _LOFF(link,TVirtualSlab,iLink); |
|
756 TLinAddr addr = slab->Alloc(aSizeShift); |
|
757 if(addr) |
|
758 { |
|
759 aAddr = addr; |
|
760 return KErrNone; |
|
761 } |
|
762 } |
|
763 TVirtualSlab* slab = NewSlab(0,aSlabType); |
|
764 if(!slab) |
|
765 return KErrNoMemory; |
|
766 TLinAddr addr = slab->Alloc(aSizeShift); |
|
767 if(!addr) |
|
768 return KErrNoMemory; |
|
769 aAddr = addr; |
|
770 return KErrNone; |
|
771 } |
|
772 |
|
773 TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask); |
|
774 if(!slab) |
|
775 { |
|
776 slab = NewSlab(aAddr,aSlabType); |
|
777 if(!slab) |
|
778 return KErrNoMemory; |
|
779 } |
|
780 else |
|
781 { |
|
782 if(slab->SlabType()!=aSlabType) |
|
783 return KErrAlreadyExists; // slab is of incompatible type |
|
784 } |
|
785 return slab->Alloc(aAddr,aSizeShift); |
|
786 } |
|
787 |
|
788 |
|
789 void RVirtualAllocSlabSet::Free(TLinAddr aAddr, TUint aSizeShift) |
|
790 { |
|
791 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift); |
|
792 |
|
793 TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask); |
|
794 if(slab) |
|
795 if(slab->Free(aAddr,aSizeShift)) |
|
796 DeleteSlab(slab); |
|
797 } |
|
798 |
|
799 |
|
800 TBool RVirtualAllocSlabSet::CheckSlabType(TLinAddr aAddr, TUint aSizeShift, TUint aSlabType) |
|
801 { |
|
802 __NK_ASSERT_DEBUG(aSizeShift>=KVirtualAllocShift && aSizeShift<KVirtualAllocSlabShift); |
|
803 |
|
804 TVirtualSlab* slab = (TVirtualSlab*)iSlabs.Find(aAddr&~KVirtualAllocSlabMask); |
|
805 if(!slab) |
|
806 { |
|
807 TRACE2(("RVirtualAllocSlabSet::CheckSlabType returns No Slab")); |
|
808 return false; |
|
809 } |
|
810 |
|
811 if(slab->iSlabType!=aSlabType) |
|
812 { |
|
813 TRACE2(("RVirtualAllocSlabSet::CheckSlabType returns Wrong Type")); |
|
814 return false; |
|
815 } |
|
816 |
|
817 return true; |
|
818 } |
|
819 |
|
820 |
|
821 // |
|
822 // RVirtualAllocator |
|
823 // |
|
824 |
|
825 RVirtualAllocator::RVirtualAllocator() |
|
826 : iBase(0), iSize(0), iAllocator(0), iSlabSet(0) |
|
827 {} |
|
828 |
|
829 |
|
830 RVirtualAllocator::~RVirtualAllocator() |
|
831 { |
|
832 __NK_ASSERT_DEBUG(iAllocator==0 || iAllocator->iAvail==iAllocator->iSize); // should be empty |
|
833 Kern::Free(iAllocator); |
|
834 Kern::Free(iSlabSet); |
|
835 } |
|
836 |
|
837 |
|
838 TInt RVirtualAllocator::Construct(TLinAddr aStart, TLinAddr aEnd, TUint aNumSlabTypes, DMutex*& aWriteLock) |
|
839 { |
|
840 if((aStart|aEnd)&KVirtualAllocSlabMask) |
|
841 return KErrArgument; // region not aligned to KVirtualAllocSlabSize |
|
842 TUint bitSize = (aEnd-aStart)>>KVirtualAllocSlabShift; |
|
843 iAllocator = TBitMapAllocator::New(bitSize, ETrue); |
|
844 if(!iAllocator) |
|
845 return KErrNoMemory; |
|
846 iSlabSet = RVirtualAllocSlabSet::New(this,aNumSlabTypes,aWriteLock); |
|
847 if(!iSlabSet) |
|
848 return KErrNoMemory; |
|
849 iBase = aStart; |
|
850 iSize = aEnd-aStart; |
|
851 return KErrNone; |
|
852 } |
|
853 |
|
854 |
|
855 TUint RVirtualAllocator::AdjustRegion(TLinAddr& aAddr, TUint& aSize) |
|
856 { |
|
857 TLinAddr first = aAddr; |
|
858 TLinAddr last = (aAddr+aSize-1); |
|
859 TLinAddr dif = first^last; |
|
860 TUint granularity = KVirtualAllocShift; |
|
861 while(dif>>granularity && ++granularity<KVirtualAllocSlabShift) |
|
862 {} |
|
863 first >>= granularity; |
|
864 last >>= granularity; |
|
865 aAddr = first<<granularity; |
|
866 aSize = (last-first+1)<<granularity; |
|
867 return granularity; |
|
868 } |
|
869 |
|
870 |
|
871 TInt RVirtualAllocator::Alloc(TLinAddr& aAddr, TUint& aSize, TLinAddr aRequestedAddr, TUint aRequestedSize, TUint aSlabType) |
|
872 { |
|
873 TRACE2(("RVirtualAllocator::Alloc(?,?,0x%08x,0x%08x,%d)",aRequestedAddr,aRequestedSize,aSlabType)); |
|
874 |
|
875 if(!aRequestedSize) |
|
876 { |
|
877 TRACE2(("RVirtualAllocator::Alloc zero size")); |
|
878 return KErrArgument; |
|
879 } |
|
880 |
|
881 aAddr = aRequestedAddr; |
|
882 aSize = aRequestedSize; |
|
883 TUint align = AdjustRegion(aAddr,aSize); |
|
884 TRACE2(("RVirtualAllocator::Alloc adjusted to 0x%08x+0x%08x, align=%d",aAddr,aSize,align)); |
|
885 |
|
886 if(align<KVirtualAllocSlabShift) |
|
887 return iSlabSet->Alloc(aAddr,align,aSlabType); |
|
888 |
|
889 __NK_ASSERT_DEBUG(align==KVirtualAllocSlabShift); |
|
890 TUint size = aSize>>KVirtualAllocSlabShift; |
|
891 |
|
892 if(!aAddr) |
|
893 { |
|
894 TInt r = iAllocator->AllocConsecutive(size, EFalse); |
|
895 if(r>=0) |
|
896 { |
|
897 iAllocator->Alloc(r, size); |
|
898 aAddr = iBase+(r<<KVirtualAllocSlabShift); |
|
899 return KErrNone; |
|
900 } |
|
901 return KErrNoMemory; |
|
902 } |
|
903 |
|
904 // specific address requested... |
|
905 if(!InRange(aAddr,aSize)) |
|
906 { |
|
907 TRACE2(("RVirtualAllocator::Alloc not in range")); |
|
908 return KErrArgument; |
|
909 } |
|
910 |
|
911 TUint offset = TUint(aAddr-iBase)>>KVirtualAllocSlabShift; |
|
912 if(!iAllocator->NotFree(offset,size)) |
|
913 { |
|
914 iAllocator->Alloc(offset,size); |
|
915 return KErrNone; |
|
916 } |
|
917 else |
|
918 { |
|
919 TRACE2(("RVirtualAllocator::Alloc already allocated!")); |
|
920 return KErrAlreadyExists; |
|
921 } |
|
922 } |
|
923 |
|
924 |
|
925 void RVirtualAllocator::Free(TLinAddr aAddr, TUint aSize) |
|
926 { |
|
927 if(!aSize) |
|
928 return; |
|
929 |
|
930 TRACE2(("RVirtualAllocator::Free(0x%08x,0x%08x)",aAddr,aSize)); |
|
931 |
|
932 TUint align = AdjustRegion(aAddr,aSize); |
|
933 TRACE2(("RVirtualAllocator::Free adjusted to 0x%08x+0x%08x, align=%d",aAddr,aSize,align)); |
|
934 |
|
935 if(!InRange(aAddr,aSize)) |
|
936 { |
|
937 TRACE2(("RVirtualAllocator::Free invalid region")); |
|
938 __NK_ASSERT_ALWAYS(0); |
|
939 return; // invalid region |
|
940 } |
|
941 |
|
942 if(align<KVirtualAllocSlabShift) |
|
943 { |
|
944 iSlabSet->Free(aAddr,align); |
|
945 return; |
|
946 } |
|
947 |
|
948 __NK_ASSERT_DEBUG(align==KVirtualAllocSlabShift); |
|
949 TUint offset = (aAddr-iBase)>>KVirtualAllocSlabShift; |
|
950 TUint size = aSize>>KVirtualAllocSlabShift; |
|
951 iAllocator->Free(offset,size); |
|
952 } |
|
953 |
|
954 |
|
955 TBool RVirtualAllocator::CheckSlabType(TLinAddr aAddr, TUint aSize, TUint aSlabType) |
|
956 { |
|
957 TRACE2(("RVirtualAllocator::CheckSlabType(0x%08x,0x%08x,%d)",aAddr,aSize,aSlabType)); |
|
958 if(!aSize) |
|
959 return false; |
|
960 |
|
961 TUint align = AdjustRegion(aAddr,aSize); |
|
962 |
|
963 if(!InRange(aAddr,aSize)) |
|
964 { |
|
965 TRACE2(("RVirtualAllocator::CheckSlabType not in range")); |
|
966 return false; |
|
967 } |
|
968 |
|
969 if(align<KVirtualAllocSlabShift) |
|
970 { |
|
971 return iSlabSet->CheckSlabType(aAddr,align,aSlabType); |
|
972 } |
|
973 else |
|
974 { |
|
975 return true; |
|
976 } |
|
977 } |
|
978 |
|
979 |
|
980 // |
|
981 // RBackwardsVirtualAllocator |
|
982 // |
|
983 |
|
984 TInt RBackwardsVirtualAllocator::Alloc(TLinAddr& aAddr, TUint& aSize, TLinAddr aRequestedAddr, TUint aRequestedSize, TUint aSlabType) |
|
985 { |
|
986 if(aRequestedAddr) |
|
987 aRequestedAddr = (iBase+iSize)-(aRequestedAddr+aRequestedSize-iBase); |
|
988 TInt r = RVirtualAllocator::Alloc(aAddr,aSize,aRequestedAddr,aRequestedSize,aSlabType); |
|
989 if(r==KErrNone) |
|
990 aAddr = (iBase+iSize)-(aAddr+aSize-iBase); |
|
991 return r; |
|
992 } |
|
993 |
|
994 |
|
995 void RBackwardsVirtualAllocator::Free(TLinAddr aAddr, TUint aSize) |
|
996 { |
|
997 RVirtualAllocator::Free((iBase+iSize)-(aAddr+aSize-iBase),aSize); |
|
998 } |
|
999 |
|
1000 |