Rev 74 | Rev 77 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 74 | Rev 76 | ||
|---|---|---|---|
| Line 36... | Line 36... | ||
| 36 | allocated or deallocated. However, this does not represent a significant |
36 | allocated or deallocated. However, this does not represent a significant |
| 37 | performance problem as it is expected that the number of zones will be |
37 | performance problem as it is expected that the number of zones will be |
| 38 | rather low. Moreover, most architectures merge all zones into |
38 | rather low. Moreover, most architectures merge all zones into |
| 39 | one.</para> |
39 | one.</para> |
| 40 | 40 | ||
| 41 | <para>For each physical memory frame found in a zone, there is a frame |
41 | <para>Every physical memory frame in a zone, is described by a structure |
| 42 | structure that contains number of references and data used by buddy |
42 | that contains number of references and other data used by buddy |
| 43 | system.</para> |
43 | system.</para> |
| 44 | </section> |
44 | </section> |
| 45 | 45 | ||
| 46 | <section id="frame_allocator"> |
46 | <section id="frame_allocator"> |
| 47 | <indexterm> |
47 | <indexterm> |
| Line 51... | Line 51... | ||
| 51 | <title>Frame allocator</title> |
51 | <title>Frame allocator</title> |
| 52 | 52 | ||
| 53 | <para>The frame allocator satisfies kernel requests to allocate |
53 | <para>The frame allocator satisfies kernel requests to allocate |
| 54 | power-of-two sized blocks of physical memory. Because of zonal |
54 | power-of-two sized blocks of physical memory. Because of zonal |
| 55 | organization of physical memory, the frame allocator is always working |
55 | organization of physical memory, the frame allocator is always working |
| 56 | within a context of some frame zone. In order to carry out the |
56 | within a context of a particular frame zone. In order to carry out the |
| 57 | allocation requests, the frame allocator is tightly integrated with the |
57 | allocation requests, the frame allocator is tightly integrated with the |
| 58 | buddy system belonging to the zone. The frame allocator is also |
58 | buddy system belonging to the zone. The frame allocator is also |
| 59 | responsible for updating information about the number of free and busy |
59 | responsible for updating information about the number of free and busy |
| 60 | frames in the zone. <figure> |
60 | frames in the zone. <figure> |
| 61 | <mediaobject id="frame_alloc"> |
61 | <mediaobject id="frame_alloc"> |
| Line 278... | Line 278... | ||
| 278 | <title>Allocation</title> |
278 | <title>Allocation</title> |
| 279 | 279 | ||
| 280 | <para><emphasis>Step 1.</emphasis> When an allocation request |
280 | <para><emphasis>Step 1.</emphasis> When an allocation request |
| 281 | comes, the slab allocator checks availability of memory in the |
281 | comes, the slab allocator checks availability of memory in the |
| 282 | current magazine of the local processor magazine cache. If the |
282 | current magazine of the local processor magazine cache. If the |
| 283 | available memory is there, the allocator just pops the magazine |
283 | available memory is there, the allocator just pops the object from |
| 284 | and returns pointer to the object.</para> |
284 | magazine and returns it.</para> |
| 285 | 285 | ||
| 286 | <para><emphasis>Step 2.</emphasis> If the current magazine in the |
286 | <para><emphasis>Step 2.</emphasis> If the current magazine in the |
| 287 | processor magazine cache is empty, the allocator will attempt to |
287 | processor magazine cache is empty, the allocator will attempt to |
| 288 | swap it with the last magazine from the cache and return to the |
288 | swap it with the last magazine from the cache and return to the |
| 289 | first step. If also the last magazine is empty, the algorithm will |
289 | first step. If also the last magazine is empty, the algorithm will |
| Line 304... | Line 304... | ||
| 304 | <formalpara> |
304 | <formalpara> |
| 305 | <title>Deallocation</title> |
305 | <title>Deallocation</title> |
| 306 | 306 | ||
| 307 | <para><emphasis>Step 1.</emphasis> During a deallocation request, |
307 | <para><emphasis>Step 1.</emphasis> During a deallocation request, |
| 308 | the slab allocator checks if the current magazine of the local |
308 | the slab allocator checks if the current magazine of the local |
| 309 | processor magazine cache is not full. If yes, the pointer to the |
309 | processor magazine cache is not full. If it is, the pointer to the |
| 310 | objects is just pushed into the magazine and the algorithm |
310 | objects is just pushed into the magazine and the algorithm |
| 311 | returns.</para> |
311 | returns.</para> |
| 312 | 312 | ||
| 313 | <para><emphasis>Step 2.</emphasis> If the current magazine is |
313 | <para><emphasis>Step 2.</emphasis> If the current magazine is |
| 314 | full, the allocator will attempt to swap it with the last magazine |
314 | full, the allocator will attempt to swap it with the last magazine |
| Line 316... | Line 316... | ||
| 316 | magazine is empty, the algorithm will fall through to Step |
316 | magazine is empty, the algorithm will fall through to Step |
| 317 | 3.</para> |
317 | 3.</para> |
| 318 | 318 | ||
| 319 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
319 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
| 320 | situation when both magazines in the processor magazine cache are |
320 | situation when both magazines in the processor magazine cache are |
| - | 321 | full. The allocator tries to allocate a new empty magazine and |
|
| 321 | full. The allocator moves one magazine to the shared list of full |
322 | flush one of the full magazines to the shared list of full |
| 322 | magazines. The algoritm continues with Step 1.</para> |
323 | magazines. If it is successfull, the algoritm continues with Step |
| - | 324 | 1.</para> |
|
| - | 325 | ||
| - | 326 | <para><emphasis>Step 4. </emphasis>In case of low memory condition |
|
| - | 327 | when the allocation of empty magazine fails, the object is moved |
|
| - | 328 | directly into slab. In the worst case object deallocation does not |
|
| - | 329 | need to allocate any additional memory.</para> |
|
| 323 | </formalpara> |
330 | </formalpara> |
| 324 | </section> |
331 | </section> |
| 325 | </section> |
332 | </section> |
| 326 | </section> |
333 | </section> |
| 327 | </section> |
334 | </section> |
| Line 401... | Line 408... | ||
| 401 | <secondary>- ASID</secondary> |
408 | <secondary>- ASID</secondary> |
| 402 | </indexterm> |
409 | </indexterm> |
| 403 | 410 | ||
| 404 | <title>Address Space ID (ASID)</title> |
411 | <title>Address Space ID (ASID)</title> |
| 405 | 412 | ||
| 406 | <para>When switching to the different task, kernel also require to |
413 | <para>Every task in the operating system has it's own view of the |
| 407 | switch mappings to the different address space. In case TLB cannot |
414 | virtual memory. When performing context switch between different |
| 408 | distinguish address space mappings, all mapping information in TLB |
415 | tasks, the kernel must switch the address space mapping as well. As |
| 409 | from the old address space must be flushed, which can create certain |
416 | modern processors perform very aggressive caching of virtual mappings, |
| 410 | uncessary overhead during the task switching. To avoid this, some |
417 | flushing the complete TLB on every context switch would be very |
| 411 | architectures have capability to segregate different address spaces on |
418 | inefficient. To avoid such performance penalty, some architectures |
| 412 | hardware level introducing the address space identifier as a part of |
419 | introduce an address space identifier, which allows storing several |
| 413 | TLB record, telling the virtual address space translation unit to |
- | |
| 414 | which address space this record is applicable.</para> |
420 | different mappings inside TLB.</para> |
| 415 | 421 | ||
| 416 | <para>HelenOS kernel can take advantage of this hardware supported |
422 | <para>HelenOS kernel can take advantage of this hardware support by |
| 417 | identifier by having an ASID abstraction which is somehow related to |
423 | having an ASID abstraction. I.e. on ia64 kernel ASID is derived from |
| 418 | the corresponding architecture identifier. I.e. on ia64 kernel ASID is |
- | |
| 419 | derived from RID (region identifier) and on the mips32 kernel ASID is |
424 | RID (region identifier) and on the mips32 kernel ASID is actually the |
| 420 | actually the hardware identifier. As expected, this ASID information |
425 | hardware identifier. As expected, this ASID information record is the |
| 421 | record is the part of <emphasis>as_t</emphasis> structure.</para> |
426 | part of <emphasis>as_t</emphasis> structure.</para> |
| 422 | 427 | ||
| 423 | <para>Due to the hardware limitations, hardware ASID has limited |
428 | <para>Due to the hardware limitations, hardware ASID has limited |
| 424 | length from 8 bits on ia64 to 24 bits on mips32, which makes it |
429 | length from 8 bits on ia64 to 24 bits on mips32, which makes it |
| 425 | impossible to use it as unique address space identifier for all tasks |
430 | impossible to use it as unique address space identifier for all tasks |
| 426 | running in the system. In such situations special ASID stealing |
431 | running in the system. In such situations special ASID stealing |