2 * Copyright (c) 2001-2005 Jakub Jermar
3 * Copyright (c) 2005 Sergey Bondari
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * - Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * - The name of the author may not be used to endorse or promote products
16 * derived from this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 /** @addtogroup genericmm
36 * @brief Physical frame allocator.
38 * This file contains the physical frame allocator and memory zone management.
39 * The frame allocator is built on top of the buddy allocator.
47 * In order to access particular zone, the process must first lock
48 * the zones.lock, then lock the zone and then unlock the zones.lock.
49 * This insures, that we can fiddle with the zones in runtime without
50 * affecting the processes.
54 #include <arch/types.h>
60 #include <synch/spinlock.h>
71 count_t refcount
; /**< tracking of shared frames */
72 uint8_t buddy_order
; /**< buddy system block order */
73 link_t buddy_link
; /**< link to the next free block inside one order */
74 void *parent
; /**< If allocated by slab, this points there */
78 SPINLOCK_DECLARE(lock
); /**< this lock protects everything below */
79 pfn_t base
; /**< frame_no of the first frame in the frames array */
80 count_t count
; /**< Size of zone */
82 frame_t
*frames
; /**< array of frame_t structures in this zone */
83 count_t free_count
; /**< number of free frame_t structures */
84 count_t busy_count
; /**< number of busy frame_t structures */
86 buddy_system_t
*buddy_system
; /**< buddy system for the zone */
91 * The zoneinfo.lock must be locked when accessing zoneinfo structure.
92 * Some of the attributes in zone_t structures are 'read-only'
96 SPINLOCK_DECLARE(lock
);
98 zone_t
*info
[ZONES_MAX
];
101 static zones_t zones
;
104 /*********************************/
105 /* Helper functions */
106 static inline index_t
frame_index(zone_t
*zone
, frame_t
*frame
)
108 return (index_t
)(frame
- zone
->frames
);
110 static inline index_t
frame_index_abs(zone_t
*zone
, frame_t
*frame
)
112 return (index_t
)(frame
- zone
->frames
) + zone
->base
;
114 static inline int frame_index_valid(zone_t
*zone
, index_t index
)
116 return index
>= 0 && index
< zone
->count
;
119 /** Compute pfn_t from frame_t pointer & zone pointer */
120 static index_t
make_frame_index(zone_t
*zone
, frame_t
*frame
)
122 return frame
- zone
->frames
;
125 /** Initialize frame structure
127 * Initialize frame structure.
129 * @param frame Frame structure to be initialized.
131 static void frame_initialize(frame_t
*frame
)
134 frame
->buddy_order
= 0;
137 /*************************************/
138 /* Zoneinfo functions */
141 * Insert-sort zone into zones list
143 * @param newzone New zone to be inserted into zone list
144 * @return zone number on success, -1 on error
146 static int zones_add_zone(zone_t
*newzone
)
152 ipl
= interrupts_disable();
153 spinlock_lock(&zones
.lock
);
155 if (zones
.count
+ 1 == ZONES_MAX
)
156 panic("Maximum zone(%d) count exceeded.", ZONES_MAX
);
157 for (i
= 0; i
< zones
.count
; i
++) {
158 /* Check for overflow */
160 if (overlaps(newzone
->base
,newzone
->count
,
161 z
->base
, z
->count
)) {
162 printf("Zones overlap!\n");
165 if (newzone
->base
< z
->base
)
168 /* Move other zones up */
169 for (j
= i
;j
< zones
.count
; j
++)
170 zones
.info
[j
+ 1] = zones
.info
[j
];
171 zones
.info
[i
] = newzone
;
173 spinlock_unlock(&zones
.lock
);
174 interrupts_restore(ipl
);
180 * Try to find a zone where can we find the frame
182 * Assume interrupts are disabled.
184 * @param frame Frame number contained in zone
185 * @param pzone If not null, it is used as zone hint. Zone index
186 * is filled into the variable on success.
187 * @return Pointer to locked zone containing frame
189 static zone_t
* find_zone_and_lock(pfn_t frame
, unsigned int *pzone
)
192 unsigned int hint
= pzone
? *pzone
: 0;
195 spinlock_lock(&zones
.lock
);
197 if (hint
>= zones
.count
|| hint
< 0)
203 spinlock_lock(&z
->lock
);
204 if (z
->base
<= frame
&& z
->base
+ z
->count
> frame
) {
205 spinlock_unlock(&zones
.lock
); /* Unlock the global lock */
210 spinlock_unlock(&z
->lock
);
213 if (i
>= zones
.count
)
217 spinlock_unlock(&zones
.lock
);
221 /** @return True if zone can allocate specified order */
222 static int zone_can_alloc(zone_t
*z
, uint8_t order
)
224 return buddy_system_can_alloc(z
->buddy_system
, order
);
227 /** Find and lock zone that can allocate order frames.
229 * Assume interrupts are disabled.
231 * @param order Size (2^order) of free space we are trying to find
232 * @param pzone Pointer to preferred zone or NULL, on return contains zone number
234 static zone_t
* find_free_zone_and_lock(uint8_t order
, unsigned int *pzone
)
238 unsigned int hint
= pzone
? *pzone
: 0;
240 spinlock_lock(&zones
.lock
);
241 if (hint
>= zones
.count
)
247 spinlock_lock(&z
->lock
);
249 /* Check if the zone has 2^order frames area available */
250 if (zone_can_alloc(z
, order
)) {
251 spinlock_unlock(&zones
.lock
);
256 spinlock_unlock(&z
->lock
);
257 if (++i
>= zones
.count
)
260 spinlock_unlock(&zones
.lock
);
264 /**************************/
265 /* Buddy system functions */
266 /**************************/
268 /** Buddy system find_block implementation
270 * Find block that is parent of current list.
271 * That means go to lower addresses, until such block is found
273 * @param order - Order of parent must be different then this parameter!!
275 static link_t
*zone_buddy_find_block(buddy_system_t
*b
, link_t
*child
,
282 frame
= list_get_instance(child
, frame_t
, buddy_link
);
283 zone
= (zone_t
*) b
->data
;
285 index
= frame_index(zone
, frame
);
287 if (zone
->frames
[index
].buddy_order
!= order
) {
288 return &zone
->frames
[index
].buddy_link
;
290 } while(index
-- > 0);
294 static void zone_buddy_print_id(buddy_system_t
*b
, link_t
*block
)
300 frame
= list_get_instance(block
, frame_t
, buddy_link
);
301 zone
= (zone_t
*) b
->data
;
302 index
= frame_index(zone
, frame
);
303 printf("%zd", index
);
306 /** Buddy system find_buddy implementation
308 * @param b Buddy system.
309 * @param block Block for which buddy should be found
311 * @return Buddy for given block if found
313 static link_t
* zone_buddy_find_buddy(buddy_system_t
*b
, link_t
* block
)
318 bool is_left
, is_right
;
320 frame
= list_get_instance(block
, frame_t
, buddy_link
);
321 zone
= (zone_t
*) b
->data
;
322 ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone
, frame
), frame
->buddy_order
));
324 is_left
= IS_BUDDY_LEFT_BLOCK_ABS(zone
, frame
);
325 is_right
= IS_BUDDY_RIGHT_BLOCK_ABS(zone
, frame
);
327 ASSERT(is_left
^ is_right
);
329 index
= (frame_index(zone
, frame
)) + (1 << frame
->buddy_order
);
330 } else { /* if (is_right) */
331 index
= (frame_index(zone
, frame
)) - (1 << frame
->buddy_order
);
334 if (frame_index_valid(zone
, index
)) {
335 if (zone
->frames
[index
].buddy_order
== frame
->buddy_order
&&
336 zone
->frames
[index
].refcount
== 0) {
337 return &zone
->frames
[index
].buddy_link
;
344 /** Buddy system bisect implementation
346 * @param b Buddy system.
347 * @param block Block to bisect
349 * @return right block
351 static link_t
* zone_buddy_bisect(buddy_system_t
*b
, link_t
* block
) {
352 frame_t
* frame_l
, * frame_r
;
354 frame_l
= list_get_instance(block
, frame_t
, buddy_link
);
355 frame_r
= (frame_l
+ (1 << (frame_l
->buddy_order
- 1)));
357 return &frame_r
->buddy_link
;
360 /** Buddy system coalesce implementation
362 * @param b Buddy system.
363 * @param block_1 First block
364 * @param block_2 First block's buddy
366 * @return Coalesced block (actually block that represents lower address)
368 static link_t
* zone_buddy_coalesce(buddy_system_t
*b
, link_t
* block_1
,
371 frame_t
*frame1
, *frame2
;
373 frame1
= list_get_instance(block_1
, frame_t
, buddy_link
);
374 frame2
= list_get_instance(block_2
, frame_t
, buddy_link
);
376 return frame1
< frame2
? block_1
: block_2
;
379 /** Buddy system set_order implementation
381 * @param b Buddy system.
382 * @param block Buddy system block
383 * @param order Order to set
385 static void zone_buddy_set_order(buddy_system_t
*b
, link_t
* block
, uint8_t order
) {
387 frame
= list_get_instance(block
, frame_t
, buddy_link
);
388 frame
->buddy_order
= order
;
391 /** Buddy system get_order implementation
393 * @param b Buddy system.
394 * @param block Buddy system block
396 * @return Order of block
398 static uint8_t zone_buddy_get_order(buddy_system_t
*b
, link_t
* block
) {
400 frame
= list_get_instance(block
, frame_t
, buddy_link
);
401 return frame
->buddy_order
;
404 /** Buddy system mark_busy implementation
406 * @param b Buddy system
407 * @param block Buddy system block
410 static void zone_buddy_mark_busy(buddy_system_t
*b
, link_t
* block
) {
413 frame
= list_get_instance(block
, frame_t
, buddy_link
);
417 /** Buddy system mark_available implementation
419 * @param b Buddy system
420 * @param block Buddy system block
423 static void zone_buddy_mark_available(buddy_system_t
*b
, link_t
* block
) {
425 frame
= list_get_instance(block
, frame_t
, buddy_link
);
429 static buddy_system_operations_t zone_buddy_system_operations
= {
430 .find_buddy
= zone_buddy_find_buddy
,
431 .bisect
= zone_buddy_bisect
,
432 .coalesce
= zone_buddy_coalesce
,
433 .set_order
= zone_buddy_set_order
,
434 .get_order
= zone_buddy_get_order
,
435 .mark_busy
= zone_buddy_mark_busy
,
436 .mark_available
= zone_buddy_mark_available
,
437 .find_block
= zone_buddy_find_block
,
438 .print_id
= zone_buddy_print_id
445 /** Allocate frame in particular zone
447 * Assume zone is locked
448 * Panics if allocation is impossible.
450 * @param zone Zone to allocate from.
451 * @param order Allocate exactly 2^order frames.
453 * @return Frame index in zone
456 static pfn_t
zone_frame_alloc(zone_t
*zone
, uint8_t order
)
462 /* Allocate frames from zone buddy system */
463 tmp
= buddy_system_alloc(zone
->buddy_system
, order
);
467 /* Update zone information. */
468 zone
->free_count
-= (1 << order
);
469 zone
->busy_count
+= (1 << order
);
471 /* Frame will be actually a first frame of the block. */
472 frame
= list_get_instance(tmp
, frame_t
, buddy_link
);
474 /* get frame address */
475 v
= make_frame_index(zone
, frame
);
479 /** Free frame from zone
481 * Assume zone is locked
483 * @param zone Pointer to zone from which the frame is to be freed
484 * @param frame_idx Frame index relative to zone
486 static void zone_frame_free(zone_t
*zone
, index_t frame_idx
)
491 frame
= &zone
->frames
[frame_idx
];
493 /* remember frame order */
494 order
= frame
->buddy_order
;
496 ASSERT(frame
->refcount
);
498 if (!--frame
->refcount
) {
499 buddy_system_free(zone
->buddy_system
, &frame
->buddy_link
);
501 /* Update zone information. */
502 zone
->free_count
+= (1 << order
);
503 zone
->busy_count
-= (1 << order
);
507 /** Return frame from zone */
508 static frame_t
* zone_get_frame(zone_t
*zone
, index_t frame_idx
)
510 ASSERT(frame_idx
< zone
->count
);
511 return &zone
->frames
[frame_idx
];
514 /** Mark frame in zone unavailable to allocation */
515 static void zone_mark_unavailable(zone_t
*zone
, index_t frame_idx
)
520 frame
= zone_get_frame(zone
, frame_idx
);
523 link
= buddy_system_alloc_block(zone
->buddy_system
,
532 * Expect zone_t *z to point to space at least zone_conf_size large
534 * Assume z1 & z2 are locked
536 * @param z Target zone structure pointer
537 * @param z1 Zone to merge
538 * @param z2 Zone to merge
540 static void _zone_merge(zone_t
*z
, zone_t
*z1
, zone_t
*z2
)
548 ASSERT(!overlaps(z1
->base
,z1
->count
,z2
->base
,z2
->count
));
549 ASSERT(z1
->base
< z2
->base
);
551 spinlock_initialize(&z
->lock
, "zone_lock");
553 z
->count
= z2
->base
+z2
->count
- z1
->base
;
554 z
->flags
= z1
->flags
& z2
->flags
;
556 z
->free_count
= z1
->free_count
+ z2
->free_count
;
557 z
->busy_count
= z1
->busy_count
+ z2
->busy_count
;
559 max_order
= fnzb(z
->count
);
561 z
->buddy_system
= (buddy_system_t
*)&z
[1];
562 buddy_system_create(z
->buddy_system
, max_order
,
563 &zone_buddy_system_operations
,
566 z
->frames
= (frame_t
*)((uint8_t *) z
->buddy_system
+ buddy_conf_size(max_order
));
567 for (i
= 0; i
< z
->count
; i
++) {
568 /* This marks all frames busy */
569 frame_initialize(&z
->frames
[i
]);
571 /* Copy frames from both zones to preserve full frame orders,
572 * parents etc. Set all free frames with refcount=0 to 1, because
573 * we add all free frames to buddy allocator later again, clear
574 * order to 0. Don't set busy frames with refcount=0, as they
575 * will not be reallocated during merge and it would make later
576 * problems with allocation/free.
578 for (i
= 0; i
< z1
->count
; i
++)
579 z
->frames
[i
] = z1
->frames
[i
];
580 for (i
= 0; i
< z2
->count
; i
++) {
581 z2idx
= i
+ (z2
->base
- z1
->base
);
582 z
->frames
[z2idx
] = z2
->frames
[i
];
585 while (i
< z
->count
) {
586 if (z
->frames
[i
].refcount
) {
587 /* skip busy frames */
588 i
+= 1 << z
->frames
[i
].buddy_order
;
589 } else { /* Free frames, set refcount=1 */
590 /* All free frames have refcount=0, we need not
591 * to check the order */
592 z
->frames
[i
].refcount
= 1;
593 z
->frames
[i
].buddy_order
= 0;
597 /* Add free blocks from the 2 original zones */
598 while (zone_can_alloc(z1
, 0)) {
599 frame_idx
= zone_frame_alloc(z1
, 0);
600 frame
= &z
->frames
[frame_idx
];
602 buddy_system_free(z
->buddy_system
, &frame
->buddy_link
);
604 while (zone_can_alloc(z2
, 0)) {
605 frame_idx
= zone_frame_alloc(z2
, 0);
606 frame
= &z
->frames
[frame_idx
+ (z2
->base
-z1
->base
)];
608 buddy_system_free(z
->buddy_system
, &frame
->buddy_link
);
612 /** Return old configuration frames into the zone
614 * We have several cases
615 * - the conf. data is outside of zone -> exit, shall we call frame_free??
616 * - the conf. data was created by zone_create or
617 * updated with reduce_region -> free every frame
619 * @param newzone The actual zone where freeing should occur
620 * @param oldzone Pointer to old zone configuration data that should
621 * be freed from new zone
623 static void return_config_frames(zone_t
*newzone
, zone_t
*oldzone
)
630 pfn
= ADDR2PFN((uintptr_t)KA2PA(oldzone
));
631 cframes
= SIZE2FRAMES(zone_conf_size(oldzone
->count
));
633 if (pfn
< newzone
->base
|| pfn
>= newzone
->base
+ newzone
->count
)
636 frame
= &newzone
->frames
[pfn
- newzone
->base
];
637 ASSERT(!frame
->buddy_order
);
639 for (i
= 0; i
< cframes
; i
++) {
640 newzone
->busy_count
++;
641 zone_frame_free(newzone
, pfn
+i
-newzone
->base
);
645 /** Reduce allocated block to count of order 0 frames
647 * The allocated block need 2^order frames of space. Reduce all frames
648 * in block to order 0 and free the unneeded frames. This means, that
649 * when freeing the previously allocated block starting with frame_idx,
650 * you have to free every frame.
653 * @param frame_idx Index to block
654 * @param count Allocated space in block
656 static void zone_reduce_region(zone_t
*zone
, pfn_t frame_idx
, count_t count
)
662 ASSERT(frame_idx
+ count
< zone
->count
);
664 order
= zone
->frames
[frame_idx
].buddy_order
;
665 ASSERT((count_t
) (1 << order
) >= count
);
667 /* Reduce all blocks to order 0 */
668 for (i
= 0; i
< (count_t
) (1 << order
); i
++) {
669 frame
= &zone
->frames
[i
+ frame_idx
];
670 frame
->buddy_order
= 0;
671 if (! frame
->refcount
)
673 ASSERT(frame
->refcount
== 1);
675 /* Free unneeded frames */
676 for (i
= count
; i
< (count_t
) (1 << order
); i
++) {
677 zone_frame_free(zone
, i
+ frame_idx
);
681 /** Merge zones z1 and z2
683 * - the zones must be 2 zones with no zone existing in between,
684 * which means that z2 = z1+1
686 * - When you create a new zone, the frame allocator configuration does
687 * not to be 2^order size. Once the allocator is running it is no longer
688 * possible, merged configuration data occupies more space :-/
690 void zone_merge(unsigned int z1
, unsigned int z2
)
693 zone_t
*zone1
, *zone2
, *newzone
;
694 unsigned int cframes
;
699 ipl
= interrupts_disable();
700 spinlock_lock(&zones
.lock
);
702 if (z1
< 0 || z1
>= zones
.count
|| z2
< 0 || z2
>= zones
.count
)
704 /* We can join only 2 zones with none existing inbetween */
708 zone1
= zones
.info
[z1
];
709 zone2
= zones
.info
[z2
];
710 spinlock_lock(&zone1
->lock
);
711 spinlock_lock(&zone2
->lock
);
713 cframes
= SIZE2FRAMES(zone_conf_size(zone2
->base
+zone2
->count
-zone1
->base
));
717 order
= fnzb(cframes
- 1) + 1;
719 /* Allocate zonedata inside one of the zones */
720 if (zone_can_alloc(zone1
, order
))
721 pfn
= zone1
->base
+ zone_frame_alloc(zone1
, order
);
722 else if (zone_can_alloc(zone2
, order
))
723 pfn
= zone2
->base
+ zone_frame_alloc(zone2
, order
);
727 newzone
= (zone_t
*) PA2KA(PFN2ADDR(pfn
));
729 _zone_merge(newzone
, zone1
, zone2
);
731 /* Free unneeded config frames */
732 zone_reduce_region(newzone
, pfn
- newzone
->base
, cframes
);
733 /* Subtract zone information from busy frames */
734 newzone
->busy_count
-= cframes
;
736 /* Replace existing zones in zoneinfo list */
737 zones
.info
[z1
] = newzone
;
738 for (i
= z2
+ 1; i
< zones
.count
; i
++)
739 zones
.info
[i
- 1] = zones
.info
[i
];
742 /* Free old zone information */
743 return_config_frames(newzone
, zone1
);
744 return_config_frames(newzone
, zone2
);
746 /* Nobody is allowed to enter to zone, so we are safe
747 * to touch the spinlocks last time */
748 spinlock_unlock(&zone1
->lock
);
749 spinlock_unlock(&zone2
->lock
);
751 spinlock_unlock(&zones
.lock
);
752 interrupts_restore(ipl
);
756 * Merge all zones into one big zone
758 * It is reasonable to do this on systems whose bios reports parts in chunks,
759 * so that we could have 1 zone (it's faster).
761 void zone_merge_all(void)
763 int count
= zones
.count
;
765 while (zones
.count
> 1 && --count
) {
771 /** Create frame zone
773 * Create new frame zone.
775 * @param start Physical address of the first frame within the zone.
776 * @param count Count of frames in zone
777 * @param z Address of configuration information of zone
778 * @param flags Zone flags.
780 * @return Initialized zone.
782 static void zone_construct(pfn_t start
, count_t count
, zone_t
*z
, int flags
)
787 spinlock_initialize(&z
->lock
, "zone_lock");
791 z
->free_count
= count
;
795 * Compute order for buddy system, initialize
797 max_order
= fnzb(count
);
798 z
->buddy_system
= (buddy_system_t
*)&z
[1];
800 buddy_system_create(z
->buddy_system
, max_order
,
801 &zone_buddy_system_operations
,
804 /* Allocate frames _after_ the conframe */
806 z
->frames
= (frame_t
*)((uint8_t *) z
->buddy_system
+ buddy_conf_size(max_order
));
807 for (i
= 0; i
< count
; i
++) {
808 frame_initialize(&z
->frames
[i
]);
811 /* Stuffing frames */
812 for (i
= 0; i
< count
; i
++) {
813 z
->frames
[i
].refcount
= 0;
814 buddy_system_free(z
->buddy_system
, &z
->frames
[i
].buddy_link
);
818 /** Compute configuration data size for zone
820 * @param count Size of zone in frames
821 * @return Size of zone configuration info (in bytes)
823 uintptr_t zone_conf_size(count_t count
)
825 int size
= sizeof(zone_t
) + count
*sizeof(frame_t
);
828 max_order
= fnzb(count
);
829 size
+= buddy_conf_size(max_order
);
833 /** Create and add zone to system
835 * @param start First frame number (absolute)
836 * @param count Size of zone in frames
837 * @param confframe Where configuration frames are supposed to be.
838 * Automatically checks, that we will not disturb the
839 * kernel and possibly init.
840 * If confframe is given _outside_ this zone, it is expected,
841 * that the area is already marked BUSY and big enough
842 * to contain zone_conf_size() amount of data.
843 * If the confframe is inside the area, the zone free frame
844 * information is modified not to include it.
846 * @return Zone number or -1 on error
848 int zone_create(pfn_t start
, count_t count
, pfn_t confframe
, int flags
)
856 /* Theoretically we could have here 0, practically make sure
857 * nobody tries to do that. If some platform requires, remove
861 /* If conframe is supposed to be inside our zone, then make sure
862 * it does not span kernel & init
864 confcount
= SIZE2FRAMES(zone_conf_size(count
));
865 if (confframe
>= start
&& confframe
< start
+count
) {
866 for (;confframe
< start
+ count
; confframe
++) {
867 addr
= PFN2ADDR(confframe
);
868 if (overlaps(addr
, PFN2ADDR(confcount
), KA2PA(config
.base
), config
.kernel_size
))
871 if (overlaps(addr
, PFN2ADDR(confcount
), KA2PA(config
.stack_base
), config
.stack_size
))
874 bool overlap
= false;
876 for (i
= 0; i
< init
.cnt
; i
++)
877 if (overlaps(addr
, PFN2ADDR(confcount
), KA2PA(init
.tasks
[i
].addr
), init
.tasks
[i
].size
)) {
886 if (confframe
>= start
+ count
)
887 panic("Cannot find configuration data for zone.");
890 z
= (zone_t
*)PA2KA(PFN2ADDR(confframe
));
891 zone_construct(start
, count
, z
, flags
);
892 znum
= zones_add_zone(z
);
896 /* If confdata in zone, mark as unavailable */
897 if (confframe
>= start
&& confframe
< start
+ count
)
898 for (i
= confframe
; i
< confframe
+ confcount
; i
++) {
899 zone_mark_unavailable(z
, i
- z
->base
);
904 /***************************************/
905 /* Frame functions */
907 /** Set parent of frame */
908 void frame_set_parent(pfn_t pfn
, void *data
, unsigned int hint
)
910 zone_t
*zone
= find_zone_and_lock(pfn
, &hint
);
914 zone_get_frame(zone
, pfn
-zone
->base
)->parent
= data
;
915 spinlock_unlock(&zone
->lock
);
918 void * frame_get_parent(pfn_t pfn
, unsigned int hint
)
920 zone_t
*zone
= find_zone_and_lock(pfn
, &hint
);
924 res
= zone_get_frame(zone
, pfn
- zone
->base
)->parent
;
926 spinlock_unlock(&zone
->lock
);
930 /** Allocate power-of-two frames of physical memory.
932 * @param order Allocate exactly 2^order frames.
933 * @param flags Flags for host zone selection and address processing.
934 * @param pzone Preferred zone
936 * @return Physical address of the allocated frame.
939 void * frame_alloc_generic(uint8_t order
, int flags
, unsigned int *pzone
)
947 ipl
= interrupts_disable();
950 * First, find suitable frame zone.
952 zone
= find_free_zone_and_lock(order
, pzone
);
954 /* If no memory, reclaim some slab memory,
955 if it does not help, reclaim all */
956 if (!zone
&& !(flags
& FRAME_NO_RECLAIM
)) {
957 freed
= slab_reclaim(0);
959 zone
= find_free_zone_and_lock(order
, pzone
);
961 freed
= slab_reclaim(SLAB_RECLAIM_ALL
);
963 zone
= find_free_zone_and_lock(order
, pzone
);
968 * TODO: Sleep until frames are available again.
970 interrupts_restore(ipl
);
972 if (flags
& FRAME_ATOMIC
)
975 panic("Sleep not implemented.\n");
979 v
= zone_frame_alloc(zone
, order
);
982 spinlock_unlock(&zone
->lock
);
983 interrupts_restore(ipl
);
985 if (flags
& FRAME_KA
)
986 return (void *)PA2KA(PFN2ADDR(v
));
987 return (void *)PFN2ADDR(v
);
992 * Find respective frame structure for supplied physical frame address.
993 * Decrement frame reference count.
994 * If it drops to zero, move the frame structure to free list.
996 * @param Frame Physical Address of of the frame to be freed.
998 void frame_free(uintptr_t frame
)
1002 pfn_t pfn
= ADDR2PFN(frame
);
1004 ipl
= interrupts_disable();
1007 * First, find host frame zone for addr.
1009 zone
= find_zone_and_lock(pfn
,NULL
);
1012 zone_frame_free(zone
, pfn
-zone
->base
);
1014 spinlock_unlock(&zone
->lock
);
1015 interrupts_restore(ipl
);
1018 /** Add reference to frame.
1020 * Find respective frame structure for supplied PFN and
1021 * increment frame reference count.
1023 * @param pfn Frame number of the frame to be freed.
1025 void frame_reference_add(pfn_t pfn
)
1031 ipl
= interrupts_disable();
1034 * First, find host frame zone for addr.
1036 zone
= find_zone_and_lock(pfn
,NULL
);
1039 frame
= &zone
->frames
[pfn
-zone
->base
];
1042 spinlock_unlock(&zone
->lock
);
1043 interrupts_restore(ipl
);
1046 /** Mark given range unavailable in frame zones */
1047 void frame_mark_unavailable(pfn_t start
, count_t count
)
1051 unsigned int prefzone
= 0;
1053 for (i
= 0; i
< count
; i
++) {
1054 zone
= find_zone_and_lock(start
+ i
, &prefzone
);
1055 if (!zone
) /* PFN not found */
1057 zone_mark_unavailable(zone
, start
+ i
- zone
->base
);
1059 spinlock_unlock(&zone
->lock
);
1063 /** Initialize physical memory management
1065 * Initialize physical memory managemnt.
1067 void frame_init(void)
1069 if (config
.cpu_active
== 1) {
1071 spinlock_initialize(&zones
.lock
, "zones.lock");
1073 /* Tell the architecture to create some memory */
1075 if (config
.cpu_active
== 1) {
1076 frame_mark_unavailable(ADDR2PFN(KA2PA(config
.base
)), SIZE2FRAMES(config
.kernel_size
));
1077 frame_mark_unavailable(ADDR2PFN(KA2PA(config
.stack_base
)), SIZE2FRAMES(config
.stack_size
));
1080 for (i
= 0; i
< init
.cnt
; i
++)
1081 frame_mark_unavailable(ADDR2PFN(KA2PA(init
.tasks
[i
].addr
)), SIZE2FRAMES(init
.tasks
[i
].size
));
1084 frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs
.base
)), SIZE2FRAMES(ballocs
.size
));
1086 /* Black list first frame, as allocating NULL would
1087 * fail in some places */
1088 frame_mark_unavailable(0, 1);
1094 /** Prints list of zones
1097 void zone_print_list(void) {
1098 zone_t
*zone
= NULL
;
1102 ipl
= interrupts_disable();
1103 spinlock_lock(&zones
.lock
);
1104 printf("# base address free frames busy frames\n");
1105 printf("-- ------------ ------------ ------------\n");
1106 for (i
= 0; i
< zones
.count
; i
++) {
1107 zone
= zones
.info
[i
];
1108 spinlock_lock(&zone
->lock
);
1109 printf("%-2d %12p %12zd %12zd\n", i
, PFN2ADDR(zone
->base
), zone
->free_count
, zone
->busy_count
);
1110 spinlock_unlock(&zone
->lock
);
1112 spinlock_unlock(&zones
.lock
);
1113 interrupts_restore(ipl
);
1116 /** Prints zone details.
1118 * @param num Zone base address or zone number.
1120 void zone_print_one(unsigned int num
) {
1121 zone_t
*zone
= NULL
;
1125 ipl
= interrupts_disable();
1126 spinlock_lock(&zones
.lock
);
1128 for (i
= 0; i
< zones
.count
; i
++) {
1129 if (i
== num
|| PFN2ADDR(zones
.info
[i
]->base
) == num
) {
1130 zone
= zones
.info
[i
];
1135 printf("Zone not found.\n");
1139 spinlock_lock(&zone
->lock
);
1140 printf("Memory zone information\n");
1141 printf("Zone base address: %#.*p\n", sizeof(uintptr_t) * 2, PFN2ADDR(zone
->base
));
1142 printf("Zone size: %zd frames (%zdK)\n", zone
->count
, ((zone
->count
) * FRAME_SIZE
) >> 10);
1143 printf("Allocated space: %zd frames (%zdK)\n", zone
->busy_count
, (zone
->busy_count
* FRAME_SIZE
) >> 10);
1144 printf("Available space: %zd frames (%zdK)\n", zone
->free_count
, (zone
->free_count
* FRAME_SIZE
) >> 10);
1145 buddy_system_structure_print(zone
->buddy_system
, FRAME_SIZE
);
1147 spinlock_unlock(&zone
->lock
);
1149 spinlock_unlock(&zones
.lock
);
1150 interrupts_restore(ipl
);