source: mainline/kernel/generic/src/mm/frame.c@ 2ddcc7b

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 2ddcc7b was 74c5a1ca, checked in by Martin Decky <martin@…>, 15 years ago

compact printouts
  • Property mode set to 100644
File size: 34.1 KB
Line 
1/*
2 * Copyright (c) 2001-2005 Jakub Jermar
3 * Copyright (c) 2005 Sergey Bondari
4 * Copyright (c) 2009 Martin Decky
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * - Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * - Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * - The name of the author may not be used to endorse or promote products
17 * derived from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31/** @addtogroup genericmm
32 * @{
33 */
34
35/**
36 * @file
37 * @brief Physical frame allocator.
38 *
39 * This file contains the physical frame allocator and memory zone management.
40 * The frame allocator is built on top of the buddy allocator.
41 *
42 * @see buddy.c
43 */
44
45#include <typedefs.h>
46#include <mm/frame.h>
47#include <mm/as.h>
48#include <panic.h>
49#include <debug.h>
50#include <adt/list.h>
51#include <synch/mutex.h>
52#include <synch/condvar.h>
53#include <arch/asm.h>
54#include <arch.h>
55#include <print.h>
56#include <align.h>
57#include <mm/slab.h>
58#include <bitops.h>
59#include <macros.h>
60#include <config.h>
61
62zones_t zones;
63
64/*
65 * Synchronization primitives used to sleep when there is no memory
66 * available.
67 */
68static mutex_t mem_avail_mtx;
69static condvar_t mem_avail_cv;
70static size_t mem_avail_req = 0; /**< Number of frames requested. */
71static size_t mem_avail_gen = 0; /**< Generation counter. */
72
73/********************/
74/* Helper functions */
75/********************/
76
77static inline size_t frame_index(zone_t *zone, frame_t *frame)
78{
79 return (size_t) (frame - zone->frames);
80}
81
82static inline size_t frame_index_abs(zone_t *zone, frame_t *frame)
83{
84 return (size_t) (frame - zone->frames) + zone->base;
85}
86
87static inline bool frame_index_valid(zone_t *zone, size_t index)
88{
89 return (index < zone->count);
90}
91
92static inline size_t make_frame_index(zone_t *zone, frame_t *frame)
93{
94 return (frame - zone->frames);
95}
96
97/** Initialize frame structure.
98 *
99 * @param frame Frame structure to be initialized.
100 *
101 */
102static void frame_initialize(frame_t *frame)
103{
104 frame->refcount = 1;
105 frame->buddy_order = 0;
106}
107
108/*******************/
109/* Zones functions */
110/*******************/
111
112/** Insert-sort zone into zones list.
113 *
114 * Assume interrupts are disabled and zones lock is
115 * locked.
116 *
117 * @param base Base frame of the newly inserted zone.
118 * @param count Number of frames of the newly inserted zone.
119 *
120 * @return Zone number on success, -1 on error.
121 *
122 */
123static size_t zones_insert_zone(pfn_t base, size_t count)
124{
125 if (zones.count + 1 == ZONES_MAX) {
126 printf("Maximum zone count %u exceeded!\n", ZONES_MAX);
127 return (size_t) -1;
128 }
129
130 size_t i;
131 for (i = 0; i < zones.count; i++) {
132 /* Check for overlap */
133 if (overlaps(base, count,
134 zones.info[i].base, zones.info[i].count)) {
135 printf("Zones overlap!\n");
136 return (size_t) -1;
137 }
138 if (base < zones.info[i].base)
139 break;
140 }
141
142 /* Move other zones up */
143 size_t j;
144 for (j = zones.count; j > i; j--) {
145 zones.info[j] = zones.info[j - 1];
146 zones.info[j].buddy_system->data =
147 (void *) &zones.info[j - 1];
148 }
149
150 zones.count++;
151
152 return i;
153}
154
155/** Get total available frames.
156 *
157 * Assume interrupts are disabled and zones lock is
158 * locked.
159 *
160 * @return Total number of available frames.
161 *
162 */
163#ifdef CONFIG_DEBUG
164static size_t total_frames_free(void)
165{
166 size_t total = 0;
167 size_t i;
168 for (i = 0; i < zones.count; i++)
169 total += zones.info[i].free_count;
170
171 return total;
172}
173#endif /* CONFIG_DEBUG */
174
175/** Find a zone with a given frames.
176 *
177 * Assume interrupts are disabled and zones lock is
178 * locked.
179 *
180 * @param frame Frame number contained in zone.
181 * @param count Number of frames to look for.
182 * @param hint Used as zone hint.
183 *
184 * @return Zone index or -1 if not found.
185 *
186 */
187size_t find_zone(pfn_t frame, size_t count, size_t hint)
188{
189 if (hint >= zones.count)
190 hint = 0;
191
192 size_t i = hint;
193 do {
194 if ((zones.info[i].base <= frame)
195 && (zones.info[i].base + zones.info[i].count >= frame + count))
196 return i;
197
198 i++;
199 if (i >= zones.count)
200 i = 0;
201
202 } while (i != hint);
203
204 return (size_t) -1;
205}
206
207/** @return True if zone can allocate specified order */
208static bool zone_can_alloc(zone_t *zone, uint8_t order)
209{
210 return (zone_flags_available(zone->flags)
211 && buddy_system_can_alloc(zone->buddy_system, order));
212}
213
214/** Find a zone that can allocate order frames.
215 *
216 * Assume interrupts are disabled and zones lock is
217 * locked.
218 *
219 * @param order Size (2^order) of free space we are trying to find.
220 * @param flags Required flags of the target zone.
221 * @param hind Preferred zone.
222 *
223 */
224static size_t find_free_zone(uint8_t order, zone_flags_t flags, size_t hint)
225{
226 if (hint >= zones.count)
227 hint = 0;
228
229 size_t i = hint;
230 do {
231 /*
232 * Check whether the zone meets the search criteria.
233 */
234 if ((zones.info[i].flags & flags) == flags) {
235 /*
236 * Check if the zone has 2^order frames area available.
237 */
238 if (zone_can_alloc(&zones.info[i], order))
239 return i;
240 }
241
242 i++;
243 if (i >= zones.count)
244 i = 0;
245
246 } while (i != hint);
247
248 return (size_t) -1;
249}
250
251/**************************/
252/* Buddy system functions */
253/**************************/
254
255/** Buddy system find_block implementation.
256 *
257 * Find block that is parent of current list.
258 * That means go to lower addresses, until such block is found
259 *
260 * @param order Order of parent must be different then this
261 * parameter!!
262 *
263 */
264static link_t *zone_buddy_find_block(buddy_system_t *buddy, link_t *child,
265 uint8_t order)
266{
267 frame_t *frame = list_get_instance(child, frame_t, buddy_link);
268 zone_t *zone = (zone_t *) buddy->data;
269
270 size_t index = frame_index(zone, frame);
271 do {
272 if (zone->frames[index].buddy_order != order)
273 return &zone->frames[index].buddy_link;
274 } while (index-- > 0);
275
276 return NULL;
277}
278
279/** Buddy system find_buddy implementation.
280 *
281 * @param buddy Buddy system.
282 * @param block Block for which buddy should be found.
283 *
284 * @return Buddy for given block if found.
285 *
286 */
287static link_t *zone_buddy_find_buddy(buddy_system_t *buddy, link_t *block)
288{
289 frame_t *frame = list_get_instance(block, frame_t, buddy_link);
290 zone_t *zone = (zone_t *) buddy->data;
291 ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),
292 frame->buddy_order));
293
294 bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
295
296 size_t index;
297 if (is_left) {
298 index = (frame_index(zone, frame)) +
299 (1 << frame->buddy_order);
300 } else { /* is_right */
301 index = (frame_index(zone, frame)) -
302 (1 << frame->buddy_order);
303 }
304
305 if (frame_index_valid(zone, index)) {
306 if ((zone->frames[index].buddy_order == frame->buddy_order) &&
307 (zone->frames[index].refcount == 0)) {
308 return &zone->frames[index].buddy_link;
309 }
310 }
311
312 return NULL;
313}
314
315/** Buddy system bisect implementation.
316 *
317 * @param buddy Buddy system.
318 * @param block Block to bisect.
319 *
320 * @return Right block.
321 *
322 */
323static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)
324{
325 frame_t *frame_l = list_get_instance(block, frame_t, buddy_link);
326 frame_t *frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
327
328 return &frame_r->buddy_link;
329}
330
331/** Buddy system coalesce implementation.
332 *
333 * @param buddy Buddy system.
334 * @param block_1 First block.
335 * @param block_2 First block's buddy.
336 *
337 * @return Coalesced block (actually block that represents lower
338 * address).
339 *
340 */
341static link_t *zone_buddy_coalesce(buddy_system_t *buddy, link_t *block_1,
342 link_t *block_2)
343{
344 frame_t *frame1 = list_get_instance(block_1, frame_t, buddy_link);
345 frame_t *frame2 = list_get_instance(block_2, frame_t, buddy_link);
346
347 return ((frame1 < frame2) ? block_1 : block_2);
348}
349
350/** Buddy system set_order implementation.
351 *
352 * @param buddy Buddy system.
353 * @param block Buddy system block.
354 * @param order Order to set.
355 *
356 */
357static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,
358 uint8_t order)
359{
360 list_get_instance(block, frame_t, buddy_link)->buddy_order = order;
361}
362
363/** Buddy system get_order implementation.
364 *
365 * @param buddy Buddy system.
366 * @param block Buddy system block.
367 *
368 * @return Order of block.
369 *
370 */
371static uint8_t zone_buddy_get_order(buddy_system_t *buddy, link_t *block)
372{
373 return list_get_instance(block, frame_t, buddy_link)->buddy_order;
374}
375
376/** Buddy system mark_busy implementation.
377 *
378 * @param buddy Buddy system.
379 * @param block Buddy system block.
380 *
381 */
382static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t * block)
383{
384 list_get_instance(block, frame_t, buddy_link)->refcount = 1;
385}
386
387/** Buddy system mark_available implementation.
388 *
389 * @param buddy Buddy system.
390 * @param block Buddy system block.
391 */
392static void zone_buddy_mark_available(buddy_system_t *buddy, link_t *block)
393{
394 list_get_instance(block, frame_t, buddy_link)->refcount = 0;
395}
396
397static buddy_system_operations_t zone_buddy_system_operations = {
398 .find_buddy = zone_buddy_find_buddy,
399 .bisect = zone_buddy_bisect,
400 .coalesce = zone_buddy_coalesce,
401 .set_order = zone_buddy_set_order,
402 .get_order = zone_buddy_get_order,
403 .mark_busy = zone_buddy_mark_busy,
404 .mark_available = zone_buddy_mark_available,
405 .find_block = zone_buddy_find_block
406};
407
408/******************/
409/* Zone functions */
410/******************/
411
412/** Allocate frame in particular zone.
413 *
414 * Assume zone is locked and is available for allocation.
415 * Panics if allocation is impossible.
416 *
417 * @param zone Zone to allocate from.
418 * @param order Allocate exactly 2^order frames.
419 *
420 * @return Frame index in zone.
421 *
422 */
423static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
424{
425 ASSERT(zone_flags_available(zone->flags));
426
427 /* Allocate frames from zone buddy system */
428 link_t *link = buddy_system_alloc(zone->buddy_system, order);
429
430 ASSERT(link);
431
432 /* Update zone information. */
433 zone->free_count -= (1 << order);
434 zone->busy_count += (1 << order);
435
436 /* Frame will be actually a first frame of the block. */
437 frame_t *frame = list_get_instance(link, frame_t, buddy_link);
438
439 /* Get frame address */
440 return make_frame_index(zone, frame);
441}
442
443/** Free frame from zone.
444 *
445 * Assume zone is locked and is available for deallocation.
446 *
447 * @param zone Pointer to zone from which the frame is to be freed.
448 * @param frame_idx Frame index relative to zone.
449 *
450 */
451static void zone_frame_free(zone_t *zone, size_t frame_idx)
452{
453 ASSERT(zone_flags_available(zone->flags));
454
455 frame_t *frame = &zone->frames[frame_idx];
456
457 /* Remember frame order */
458 uint8_t order = frame->buddy_order;
459
460 ASSERT(frame->refcount);
461
462 if (!--frame->refcount) {
463 buddy_system_free(zone->buddy_system, &frame->buddy_link);
464
465 /* Update zone information. */
466 zone->free_count += (1 << order);
467 zone->busy_count -= (1 << order);
468 }
469}
470
471/** Return frame from zone. */
472static frame_t *zone_get_frame(zone_t *zone, size_t frame_idx)
473{
474 ASSERT(frame_idx < zone->count);
475 return &zone->frames[frame_idx];
476}
477
478/** Mark frame in zone unavailable to allocation. */
479static void zone_mark_unavailable(zone_t *zone, size_t frame_idx)
480{
481 ASSERT(zone_flags_available(zone->flags));
482
483 frame_t *frame = zone_get_frame(zone, frame_idx);
484 if (frame->refcount)
485 return;
486
487 link_t *link __attribute__ ((unused));
488
489 link = buddy_system_alloc_block(zone->buddy_system,
490 &frame->buddy_link);
491
492 ASSERT(link);
493 zone->free_count--;
494}
495
496/** Merge two zones.
497 *
498 * Expect buddy to point to space at least zone_conf_size large.
499 * Assume z1 & z2 are locked and compatible and zones lock is
500 * locked.
501 *
502 * @param z1 First zone to merge.
503 * @param z2 Second zone to merge.
504 * @param old_z1 Original date of the first zone.
505 * @param buddy Merged zone buddy.
506 *
507 */
508static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1, buddy_system_t *buddy)
509{
510 ASSERT(zone_flags_available(zones.info[z1].flags));
511 ASSERT(zone_flags_available(zones.info[z2].flags));
512 ASSERT(zones.info[z1].flags == zones.info[z2].flags);
513 ASSERT(zones.info[z1].base < zones.info[z2].base);
514 ASSERT(!overlaps(zones.info[z1].base, zones.info[z1].count,
515 zones.info[z2].base, zones.info[z2].count));
516
517 /* Difference between zone bases */
518 pfn_t base_diff = zones.info[z2].base - zones.info[z1].base;
519
520 zones.info[z1].count = base_diff + zones.info[z2].count;
521 zones.info[z1].free_count += zones.info[z2].free_count;
522 zones.info[z1].busy_count += zones.info[z2].busy_count;
523 zones.info[z1].buddy_system = buddy;
524
525 uint8_t order = fnzb(zones.info[z1].count);
526 buddy_system_create(zones.info[z1].buddy_system, order,
527 &zone_buddy_system_operations, (void *) &zones.info[z1]);
528
529 zones.info[z1].frames =
530 (frame_t *) ((uint8_t *) zones.info[z1].buddy_system
531 + buddy_conf_size(order));
532
533 /* This marks all frames busy */
534 size_t i;
535 for (i = 0; i < zones.info[z1].count; i++)
536 frame_initialize(&zones.info[z1].frames[i]);
537
538 /* Copy frames from both zones to preserve full frame orders,
539 * parents etc. Set all free frames with refcount = 0 to 1, because
540 * we add all free frames to buddy allocator later again, clearing
541 * order to 0. Don't set busy frames with refcount = 0, as they
542 * will not be reallocated during merge and it would make later
543 * problems with allocation/free.
544 */
545 for (i = 0; i < old_z1->count; i++)
546 zones.info[z1].frames[i] = old_z1->frames[i];
547
548 for (i = 0; i < zones.info[z2].count; i++)
549 zones.info[z1].frames[base_diff + i]
550 = zones.info[z2].frames[i];
551
552 i = 0;
553 while (i < zones.info[z1].count) {
554 if (zones.info[z1].frames[i].refcount) {
555 /* Skip busy frames */
556 i += 1 << zones.info[z1].frames[i].buddy_order;
557 } else {
558 /* Free frames, set refcount = 1
559 * (all free frames have refcount == 0, we need not
560 * to check the order)
561 */
562 zones.info[z1].frames[i].refcount = 1;
563 zones.info[z1].frames[i].buddy_order = 0;
564 i++;
565 }
566 }
567
568 /* Add free blocks from the original zone z1 */
569 while (zone_can_alloc(old_z1, 0)) {
570 /* Allocate from the original zone */
571 pfn_t frame_idx = zone_frame_alloc(old_z1, 0);
572
573 /* Free the frame from the merged zone */
574 frame_t *frame = &zones.info[z1].frames[frame_idx];
575 frame->refcount = 0;
576 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
577 }
578
579 /* Add free blocks from the original zone z2 */
580 while (zone_can_alloc(&zones.info[z2], 0)) {
581 /* Allocate from the original zone */
582 pfn_t frame_idx = zone_frame_alloc(&zones.info[z2], 0);
583
584 /* Free the frame from the merged zone */
585 frame_t *frame = &zones.info[z1].frames[base_diff + frame_idx];
586 frame->refcount = 0;
587 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
588 }
589}
590
591/** Return old configuration frames into the zone.
592 *
593 * We have two cases:
594 * - The configuration data is outside the zone
595 * -> do nothing (perhaps call frame_free?)
596 * - The configuration data was created by zone_create
597 * or updated by reduce_region -> free every frame
598 *
599 * @param znum The actual zone where freeing should occur.
600 * @param pfn Old zone configuration frame.
601 * @param count Old zone frame count.
602 *
603 */
604static void return_config_frames(size_t znum, pfn_t pfn, size_t count)
605{
606 ASSERT(zone_flags_available(zones.info[znum].flags));
607
608 size_t cframes = SIZE2FRAMES(zone_conf_size(count));
609
610 if ((pfn < zones.info[znum].base)
611 || (pfn >= zones.info[znum].base + zones.info[znum].count))
612 return;
613
614 frame_t *frame __attribute__ ((unused));
615
616 frame = &zones.info[znum].frames[pfn - zones.info[znum].base];
617 ASSERT(!frame->buddy_order);
618
619 size_t i;
620 for (i = 0; i < cframes; i++) {
621 zones.info[znum].busy_count++;
622 zone_frame_free(&zones.info[znum],
623 pfn - zones.info[znum].base + i);
624 }
625}
626
627/** Reduce allocated block to count of order 0 frames.
628 *
629 * The allocated block needs 2^order frames. Reduce all frames
630 * in the block to order 0 and free the unneeded frames. This means that
631 * when freeing the previously allocated block starting with frame_idx,
632 * you have to free every frame.
633 *
634 * @param znum Zone.
635 * @param frame_idx Index the first frame of the block.
636 * @param count Allocated frames in block.
637 *
638 */
639static void zone_reduce_region(size_t znum, pfn_t frame_idx, size_t count)
640{
641 ASSERT(zone_flags_available(zones.info[znum].flags));
642 ASSERT(frame_idx + count < zones.info[znum].count);
643
644 uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;
645 ASSERT((size_t) (1 << order) >= count);
646
647 /* Reduce all blocks to order 0 */
648 size_t i;
649 for (i = 0; i < (size_t) (1 << order); i++) {
650 frame_t *frame = &zones.info[znum].frames[i + frame_idx];
651 frame->buddy_order = 0;
652 if (!frame->refcount)
653 frame->refcount = 1;
654 ASSERT(frame->refcount == 1);
655 }
656
657 /* Free unneeded frames */
658 for (i = count; i < (size_t) (1 << order); i++)
659 zone_frame_free(&zones.info[znum], i + frame_idx);
660}
661
662/** Merge zones z1 and z2.
663 *
664 * The merged zones must be 2 zones with no zone existing in between
665 * (which means that z2 = z1 + 1). Both zones must be available zones
666 * with the same flags.
667 *
668 * When you create a new zone, the frame allocator configuration does
669 * not to be 2^order size. Once the allocator is running it is no longer
670 * possible, merged configuration data occupies more space :-/
671 *
672 * The function uses
673 *
674 */
675bool zone_merge(size_t z1, size_t z2)
676{
677 irq_spinlock_lock(&zones.lock, true);
678
679 bool ret = true;
680
681 /* We can join only 2 zones with none existing inbetween,
682 * the zones have to be available and with the same
683 * set of flags
684 */
685 if ((z1 >= zones.count) || (z2 >= zones.count)
686 || (z2 - z1 != 1)
687 || (!zone_flags_available(zones.info[z1].flags))
688 || (!zone_flags_available(zones.info[z2].flags))
689 || (zones.info[z1].flags != zones.info[z2].flags)) {
690 ret = false;
691 goto errout;
692 }
693
694 pfn_t cframes = SIZE2FRAMES(zone_conf_size(
695 zones.info[z2].base - zones.info[z1].base
696 + zones.info[z2].count));
697
698 uint8_t order;
699 if (cframes == 1)
700 order = 0;
701 else
702 order = fnzb(cframes - 1) + 1;
703
704 /* Allocate merged zone data inside one of the zones */
705 pfn_t pfn;
706 if (zone_can_alloc(&zones.info[z1], order)) {
707 pfn = zones.info[z1].base + zone_frame_alloc(&zones.info[z1], order);
708 } else if (zone_can_alloc(&zones.info[z2], order)) {
709 pfn = zones.info[z2].base + zone_frame_alloc(&zones.info[z2], order);
710 } else {
711 ret = false;
712 goto errout;
713 }
714
715 /* Preserve original data from z1 */
716 zone_t old_z1 = zones.info[z1];
717 old_z1.buddy_system->data = (void *) &old_z1;
718
719 /* Do zone merging */
720 buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(pfn));
721 zone_merge_internal(z1, z2, &old_z1, buddy);
722
723 /* Free unneeded config frames */
724 zone_reduce_region(z1, pfn - zones.info[z1].base, cframes);
725
726 /* Subtract zone information from busy frames */
727 zones.info[z1].busy_count -= cframes;
728
729 /* Free old zone information */
730 return_config_frames(z1,
731 ADDR2PFN(KA2PA((uintptr_t) old_z1.frames)), old_z1.count);
732 return_config_frames(z1,
733 ADDR2PFN(KA2PA((uintptr_t) zones.info[z2].frames)),
734 zones.info[z2].count);
735
736 /* Move zones down */
737 size_t i;
738 for (i = z2 + 1; i < zones.count; i++) {
739 zones.info[i - 1] = zones.info[i];
740 zones.info[i - 1].buddy_system->data =
741 (void *) &zones.info[i - 1];
742 }
743
744 zones.count--;
745
746errout:
747 irq_spinlock_unlock(&zones.lock, true);
748
749 return ret;
750}
751
752/** Merge all mergeable zones into one big zone.
753 *
754 * It is reasonable to do this on systems where
755 * BIOS reports parts in chunks, so that we could
756 * have 1 zone (it's faster).
757 *
758 */
759void zone_merge_all(void)
760{
761 size_t i = 0;
762 while (i < zones.count) {
763 if (!zone_merge(i, i + 1))
764 i++;
765 }
766}
767
768/** Create new frame zone.
769 *
770 * @param zone Zone to construct.
771 * @param buddy Address of buddy system configuration information.
772 * @param start Physical address of the first frame within the zone.
773 * @param count Count of frames in zone.
774 * @param flags Zone flags.
775 *
776 * @return Initialized zone.
777 *
778 */
779static void zone_construct(zone_t *zone, buddy_system_t *buddy, pfn_t start,
780 size_t count, zone_flags_t flags)
781{
782 zone->base = start;
783 zone->count = count;
784 zone->flags = flags;
785 zone->free_count = count;
786 zone->busy_count = 0;
787 zone->buddy_system = buddy;
788
789 if (zone_flags_available(flags)) {
790 /*
791 * Compute order for buddy system and initialize
792 */
793 uint8_t order = fnzb(count);
794 buddy_system_create(zone->buddy_system, order,
795 &zone_buddy_system_operations, (void *) zone);
796
797 /* Allocate frames _after_ the confframe */
798
799 /* Check sizes */
800 zone->frames = (frame_t *) ((uint8_t *) zone->buddy_system +
801 buddy_conf_size(order));
802
803 size_t i;
804 for (i = 0; i < count; i++)
805 frame_initialize(&zone->frames[i]);
806
807 /* Stuffing frames */
808 for (i = 0; i < count; i++) {
809 zone->frames[i].refcount = 0;
810 buddy_system_free(zone->buddy_system, &zone->frames[i].buddy_link);
811 }
812 } else
813 zone->frames = NULL;
814}
815
816/** Compute configuration data size for zone.
817 *
818 * @param count Size of zone in frames.
819 *
820 * @return Size of zone configuration info (in bytes).
821 *
822 */
823uintptr_t zone_conf_size(size_t count)
824{
825 return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count)));
826}
827
828/** Create and add zone to system.
829 *
830 * @param start First frame number (absolute).
831 * @param count Size of zone in frames.
832 * @param confframe Where configuration frames are supposed to be.
833 * Automatically checks, that we will not disturb the
834 * kernel and possibly init. If confframe is given
835 * _outside_ this zone, it is expected, that the area is
836 * already marked BUSY and big enough to contain
837 * zone_conf_size() amount of data. If the confframe is
838 * inside the area, the zone free frame information is
839 * modified not to include it.
840 *
841 * @return Zone number or -1 on error.
842 *
843 */
844size_t zone_create(pfn_t start, size_t count, pfn_t confframe,
845 zone_flags_t flags)
846{
847 irq_spinlock_lock(&zones.lock, true);
848
849 if (zone_flags_available(flags)) { /* Create available zone */
850 /* Theoretically we could have NULL here, practically make sure
851 * nobody tries to do that. If some platform requires, remove
852 * the assert
853 */
854 ASSERT(confframe != NULL);
855
856 /* If confframe is supposed to be inside our zone, then make sure
857 * it does not span kernel & init
858 */
859 size_t confcount = SIZE2FRAMES(zone_conf_size(count));
860 if ((confframe >= start) && (confframe < start + count)) {
861 for (; confframe < start + count; confframe++) {
862 uintptr_t addr = PFN2ADDR(confframe);
863 if (overlaps(addr, PFN2ADDR(confcount),
864 KA2PA(config.base), config.kernel_size))
865 continue;
866
867 if (overlaps(addr, PFN2ADDR(confcount),
868 KA2PA(config.stack_base), config.stack_size))
869 continue;
870
871 bool overlap = false;
872 size_t i;
873 for (i = 0; i < init.cnt; i++)
874 if (overlaps(addr, PFN2ADDR(confcount),
875 KA2PA(init.tasks[i].addr),
876 init.tasks[i].size)) {
877 overlap = true;
878 break;
879 }
880 if (overlap)
881 continue;
882
883 break;
884 }
885
886 if (confframe >= start + count)
887 panic("Cannot find configuration data for zone.");
888 }
889
890 size_t znum = zones_insert_zone(start, count);
891 if (znum == (size_t) -1) {
892 irq_spinlock_unlock(&zones.lock, true);
893 return (size_t) -1;
894 }
895
896 buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(confframe));
897 zone_construct(&zones.info[znum], buddy, start, count, flags);
898
899 /* If confdata in zone, mark as unavailable */
900 if ((confframe >= start) && (confframe < start + count)) {
901 size_t i;
902 for (i = confframe; i < confframe + confcount; i++)
903 zone_mark_unavailable(&zones.info[znum],
904 i - zones.info[znum].base);
905 }
906
907 irq_spinlock_unlock(&zones.lock, true);
908
909 return znum;
910 }
911
912 /* Non-available zone */
913 size_t znum = zones_insert_zone(start, count);
914 if (znum == (size_t) -1) {
915 irq_spinlock_unlock(&zones.lock, true);
916 return (size_t) -1;
917 }
918 zone_construct(&zones.info[znum], NULL, start, count, flags);
919
920 irq_spinlock_unlock(&zones.lock, true);
921
922 return znum;
923}
924
925/*******************/
926/* Frame functions */
927/*******************/
928
929/** Set parent of frame. */
930void frame_set_parent(pfn_t pfn, void *data, size_t hint)
931{
932 irq_spinlock_lock(&zones.lock, true);
933
934 size_t znum = find_zone(pfn, 1, hint);
935
936 ASSERT(znum != (size_t) -1);
937
938 zone_get_frame(&zones.info[znum],
939 pfn - zones.info[znum].base)->parent = data;
940
941 irq_spinlock_unlock(&zones.lock, true);
942}
943
944void *frame_get_parent(pfn_t pfn, size_t hint)
945{
946 irq_spinlock_lock(&zones.lock, true);
947
948 size_t znum = find_zone(pfn, 1, hint);
949
950 ASSERT(znum != (size_t) -1);
951
952 void *res = zone_get_frame(&zones.info[znum],
953 pfn - zones.info[znum].base)->parent;
954
955 irq_spinlock_unlock(&zones.lock, true);
956
957 return res;
958}
959
960/** Allocate power-of-two frames of physical memory.
961 *
962 * @param order Allocate exactly 2^order frames.
963 * @param flags Flags for host zone selection and address processing.
964 * @param pzone Preferred zone.
965 *
966 * @return Physical address of the allocated frame.
967 *
968 */
969void *frame_alloc_generic(uint8_t order, frame_flags_t flags, size_t *pzone)
970{
971 size_t size = ((size_t) 1) << order;
972 size_t hint = pzone ? (*pzone) : 0;
973
974loop:
975 irq_spinlock_lock(&zones.lock, true);
976
977 /*
978 * First, find suitable frame zone.
979 */
980 size_t znum = find_free_zone(order,
981 FRAME_TO_ZONE_FLAGS(flags), hint);
982
983 /* If no memory, reclaim some slab memory,
984 if it does not help, reclaim all */
985 if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
986 irq_spinlock_unlock(&zones.lock, true);
987 size_t freed = slab_reclaim(0);
988 irq_spinlock_lock(&zones.lock, true);
989
990 if (freed > 0)
991 znum = find_free_zone(order,
992 FRAME_TO_ZONE_FLAGS(flags), hint);
993
994 if (znum == (size_t) -1) {
995 irq_spinlock_unlock(&zones.lock, true);
996 freed = slab_reclaim(SLAB_RECLAIM_ALL);
997 irq_spinlock_lock(&zones.lock, true);
998
999 if (freed > 0)
1000 znum = find_free_zone(order,
1001 FRAME_TO_ZONE_FLAGS(flags), hint);
1002 }
1003 }
1004
1005 if (znum == (size_t) -1) {
1006 if (flags & FRAME_ATOMIC) {
1007 irq_spinlock_unlock(&zones.lock, true);
1008 return NULL;
1009 }
1010
1011#ifdef CONFIG_DEBUG
1012 size_t avail = total_frames_free();
1013#endif
1014
1015 irq_spinlock_unlock(&zones.lock, true);
1016
1017 if (!THREAD)
1018 panic("Cannot wait for memory to become available.");
1019
1020 /*
1021 * Sleep until some frames are available again.
1022 */
1023
1024#ifdef CONFIG_DEBUG
1025 printf("Thread %" PRIu64 " waiting for %" PRIs " frames, "
1026 "%" PRIs " available.\n", THREAD->tid, size, avail);
1027#endif
1028
1029 mutex_lock(&mem_avail_mtx);
1030
1031 if (mem_avail_req > 0)
1032 mem_avail_req = min(mem_avail_req, size);
1033 else
1034 mem_avail_req = size;
1035 size_t gen = mem_avail_gen;
1036
1037 while (gen == mem_avail_gen)
1038 condvar_wait(&mem_avail_cv, &mem_avail_mtx);
1039
1040 mutex_unlock(&mem_avail_mtx);
1041
1042#ifdef CONFIG_DEBUG
1043 printf("Thread %" PRIu64 " woken up.\n", THREAD->tid);
1044#endif
1045
1046 goto loop;
1047 }
1048
1049 pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)
1050 + zones.info[znum].base;
1051
1052 irq_spinlock_unlock(&zones.lock, true);
1053
1054 if (pzone)
1055 *pzone = znum;
1056
1057 if (flags & FRAME_KA)
1058 return (void *) PA2KA(PFN2ADDR(pfn));
1059
1060 return (void *) PFN2ADDR(pfn);
1061}
1062
1063/** Free a frame.
1064 *
1065 * Find respective frame structure for supplied physical frame address.
1066 * Decrement frame reference count. If it drops to zero, move the frame
1067 * structure to free list.
1068 *
1069 * @param frame Physical Address of of the frame to be freed.
1070 *
1071 */
1072void frame_free(uintptr_t frame)
1073{
1074 irq_spinlock_lock(&zones.lock, true);
1075
1076 /*
1077 * First, find host frame zone for addr.
1078 */
1079 pfn_t pfn = ADDR2PFN(frame);
1080 size_t znum = find_zone(pfn, 1, NULL);
1081
1082 ASSERT(znum != (size_t) -1);
1083
1084 zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base);
1085
1086 irq_spinlock_unlock(&zones.lock, true);
1087
1088 /*
1089 * Signal that some memory has been freed.
1090 */
1091 mutex_lock(&mem_avail_mtx);
1092 if (mem_avail_req > 0)
1093 mem_avail_req--;
1094
1095 if (mem_avail_req == 0) {
1096 mem_avail_gen++;
1097 condvar_broadcast(&mem_avail_cv);
1098 }
1099 mutex_unlock(&mem_avail_mtx);
1100}
1101
1102/** Add reference to frame.
1103 *
1104 * Find respective frame structure for supplied PFN and
1105 * increment frame reference count.
1106 *
1107 * @param pfn Frame number of the frame to be freed.
1108 *
1109 */
1110void frame_reference_add(pfn_t pfn)
1111{
1112 irq_spinlock_lock(&zones.lock, true);
1113
1114 /*
1115 * First, find host frame zone for addr.
1116 */
1117 size_t znum = find_zone(pfn, 1, NULL);
1118
1119 ASSERT(znum != (size_t) -1);
1120
1121 zones.info[znum].frames[pfn - zones.info[znum].base].refcount++;
1122
1123 irq_spinlock_unlock(&zones.lock, true);
1124}
1125
1126/** Mark given range unavailable in frame zones.
1127 *
1128 */
1129void frame_mark_unavailable(pfn_t start, size_t count)
1130{
1131 irq_spinlock_lock(&zones.lock, true);
1132
1133 size_t i;
1134 for (i = 0; i < count; i++) {
1135 size_t znum = find_zone(start + i, 1, 0);
1136 if (znum == (size_t) -1) /* PFN not found */
1137 continue;
1138
1139 zone_mark_unavailable(&zones.info[znum],
1140 start + i - zones.info[znum].base);
1141 }
1142
1143 irq_spinlock_unlock(&zones.lock, true);
1144}
1145
1146/** Initialize physical memory management.
1147 *
1148 */
1149void frame_init(void)
1150{
1151 if (config.cpu_active == 1) {
1152 zones.count = 0;
1153 irq_spinlock_initialize(&zones.lock, "frame.zones.lock");
1154 mutex_initialize(&mem_avail_mtx, MUTEX_ACTIVE);
1155 condvar_initialize(&mem_avail_cv);
1156 }
1157
1158 /* Tell the architecture to create some memory */
1159 frame_arch_init();
1160 if (config.cpu_active == 1) {
1161 frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
1162 SIZE2FRAMES(config.kernel_size));
1163 frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)),
1164 SIZE2FRAMES(config.stack_size));
1165
1166 size_t i;
1167 for (i = 0; i < init.cnt; i++) {
1168 pfn_t pfn = ADDR2PFN(KA2PA(init.tasks[i].addr));
1169 frame_mark_unavailable(pfn,
1170 SIZE2FRAMES(init.tasks[i].size));
1171 }
1172
1173 if (ballocs.size)
1174 frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)),
1175 SIZE2FRAMES(ballocs.size));
1176
1177 /* Black list first frame, as allocating NULL would
1178 * fail in some places
1179 */
1180 frame_mark_unavailable(0, 1);
1181 }
1182}
1183
1184/** Return total size of all zones.
1185 *
1186 */
1187uint64_t zones_total_size(void)
1188{
1189 irq_spinlock_lock(&zones.lock, true);
1190
1191 uint64_t total = 0;
1192 size_t i;
1193 for (i = 0; i < zones.count; i++)
1194 total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1195
1196 irq_spinlock_unlock(&zones.lock, true);
1197
1198 return total;
1199}
1200
1201void zones_stats(uint64_t *total, uint64_t *unavail, uint64_t *busy,
1202 uint64_t *free)
1203{
1204 ASSERT(total != NULL);
1205 ASSERT(unavail != NULL);
1206 ASSERT(busy != NULL);
1207 ASSERT(free != NULL);
1208
1209 irq_spinlock_lock(&zones.lock, true);
1210
1211 *total = 0;
1212 *unavail = 0;
1213 *busy = 0;
1214 *free = 0;
1215
1216 size_t i;
1217 for (i = 0; i < zones.count; i++) {
1218 *total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1219
1220 if (zone_flags_available(zones.info[i].flags)) {
1221 *busy += (uint64_t) FRAMES2SIZE(zones.info[i].busy_count);
1222 *free += (uint64_t) FRAMES2SIZE(zones.info[i].free_count);
1223 } else
1224 *unavail += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1225 }
1226
1227 irq_spinlock_unlock(&zones.lock, true);
1228}
1229
1230/** Prints list of zones.
1231 *
1232 */
1233void zones_print_list(void)
1234{
1235#ifdef __32_BITS__
1236 printf("[nr] [base addr] [frames ] [flags ] [free frames ] [busy frames ]\n");
1237#endif
1238
1239#ifdef __64_BITS__
1240 printf("[nr] [base address ] [frames ] [flags ] [free frames ] [busy frames ]\n");
1241#endif
1242
1243 /*
1244 * Because printing may require allocation of memory, we may not hold
1245 * the frame allocator locks when printing zone statistics. Therefore,
1246 * we simply gather the statistics under the protection of the locks and
1247 * print the statistics when the locks have been released.
1248 *
1249 * When someone adds/removes zones while we are printing the statistics,
1250 * we may end up with inaccurate output (e.g. a zone being skipped from
1251 * the listing).
1252 */
1253
1254 size_t i;
1255 for (i = 0;; i++) {
1256 irq_spinlock_lock(&zones.lock, true);
1257
1258 if (i >= zones.count) {
1259 irq_spinlock_unlock(&zones.lock, true);
1260 break;
1261 }
1262
1263 uintptr_t base = PFN2ADDR(zones.info[i].base);
1264 size_t count = zones.info[i].count;
1265 zone_flags_t flags = zones.info[i].flags;
1266 size_t free_count = zones.info[i].free_count;
1267 size_t busy_count = zones.info[i].busy_count;
1268
1269 irq_spinlock_unlock(&zones.lock, true);
1270
1271 bool available = zone_flags_available(flags);
1272
1273 printf("%-4" PRIs, i);
1274
1275#ifdef __32_BITS__
1276 printf(" %10p", base);
1277#endif
1278
1279#ifdef __64_BITS__
1280 printf(" %18p", base);
1281#endif
1282
1283 printf(" %12" PRIs " %c%c%c ", count,
1284 available ? 'A' : ' ',
1285 (flags & ZONE_RESERVED) ? 'R' : ' ',
1286 (flags & ZONE_FIRMWARE) ? 'F' : ' ');
1287
1288 if (available)
1289 printf("%14" PRIs " %14" PRIs,
1290 free_count, busy_count);
1291
1292 printf("\n");
1293 }
1294}
1295
1296/** Prints zone details.
1297 *
1298 * @param num Zone base address or zone number.
1299 *
1300 */
1301void zone_print_one(size_t num)
1302{
1303 irq_spinlock_lock(&zones.lock, true);
1304 size_t znum = (size_t) -1;
1305
1306 size_t i;
1307 for (i = 0; i < zones.count; i++) {
1308 if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
1309 znum = i;
1310 break;
1311 }
1312 }
1313
1314 if (znum == (size_t) -1) {
1315 irq_spinlock_unlock(&zones.lock, true);
1316 printf("Zone not found.\n");
1317 return;
1318 }
1319
1320 uintptr_t base = PFN2ADDR(zones.info[i].base);
1321 zone_flags_t flags = zones.info[i].flags;
1322 size_t count = zones.info[i].count;
1323 size_t free_count = zones.info[i].free_count;
1324 size_t busy_count = zones.info[i].busy_count;
1325
1326 irq_spinlock_unlock(&zones.lock, true);
1327
1328 bool available = zone_flags_available(flags);
1329
1330 printf("Zone number: %" PRIs "\n", znum);
1331 printf("Zone base address: %p\n", base);
1332 printf("Zone size: %" PRIs " frames (%" PRIs " KiB)\n", count,
1333 SIZE2KB(FRAMES2SIZE(count)));
1334 printf("Zone flags: %c%c%c\n",
1335 available ? 'A' : ' ',
1336 (flags & ZONE_RESERVED) ? 'R' : ' ',
1337 (flags & ZONE_FIRMWARE) ? 'F' : ' ');
1338
1339 if (available) {
1340 printf("Allocated space: %" PRIs " frames (%" PRIs " KiB)\n",
1341 busy_count, SIZE2KB(FRAMES2SIZE(busy_count)));
1342 printf("Available space: %" PRIs " frames (%" PRIs " KiB)\n",
1343 free_count, SIZE2KB(FRAMES2SIZE(free_count)));
1344 }
1345}
1346
1347/** @}
1348 */
Note: See TracBrowser for help on using the repository browser.