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

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

initialize the zone bitmap properly
  • Property mode set to 100644
File size: 31.5 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 two-level bitmap structure.
41 *
42 */
43
44#include <typedefs.h>
45#include <mm/frame.h>
46#include <mm/reserve.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#include <str.h>
62
63#define BITMAP_BLOCK_SIZE 1024
64
65zones_t zones;
66
67/*
68 * Synchronization primitives used to sleep when there is no memory
69 * available.
70 */
71static mutex_t mem_avail_mtx;
72static condvar_t mem_avail_cv;
73static size_t mem_avail_req = 0; /**< Number of frames requested. */
74static size_t mem_avail_gen = 0; /**< Generation counter. */
75
76/********************/
77/* Helper functions */
78/********************/
79
80NO_TRACE static inline size_t frame_index(zone_t *zone, frame_t *frame)
81{
82 return (size_t) (frame - zone->frames);
83}
84
85NO_TRACE static inline size_t frame_index_abs(zone_t *zone, frame_t *frame)
86{
87 return (size_t) (frame - zone->frames) + zone->base;
88}
89
90NO_TRACE static inline bool frame_index_valid(zone_t *zone, size_t index)
91{
92 return (index < zone->count);
93}
94
95/** Initialize frame structure.
96 *
97 * @param frame Frame structure to be initialized.
98 *
99 */
100NO_TRACE static void frame_initialize(frame_t *frame)
101{
102 frame->refcount = 0;
103 frame->parent = NULL;
104}
105
106/*******************/
107/* Zones functions */
108/*******************/
109
110/** Insert-sort zone into zones list.
111 *
112 * Assume interrupts are disabled and zones lock is
113 * locked.
114 *
115 * @param base Base frame of the newly inserted zone.
116 * @param count Number of frames of the newly inserted zone.
117 *
118 * @return Zone number on success, -1 on error.
119 *
120 */
121NO_TRACE static size_t zones_insert_zone(pfn_t base, size_t count,
122 zone_flags_t flags)
123{
124 if (zones.count + 1 == ZONES_MAX) {
125 printf("Maximum zone count %u exceeded!\n", ZONES_MAX);
126 return (size_t) -1;
127 }
128
129 size_t i;
130 for (i = 0; i < zones.count; i++) {
131 /* Check for overlap */
132 if (overlaps(zones.info[i].base, zones.info[i].count,
133 base, count)) {
134
135 /*
136 * If the overlaping zones are of the same type
137 * and the new zone is completely within the previous
138 * one, then quietly ignore the new zone.
139 *
140 */
141
142 if ((zones.info[i].flags != flags) ||
143 (!iswithin(zones.info[i].base, zones.info[i].count,
144 base, count))) {
145 printf("Zone (%p, %p) overlaps "
146 "with previous zone (%p %p)!\n",
147 (void *) PFN2ADDR(base), (void *) PFN2ADDR(count),
148 (void *) PFN2ADDR(zones.info[i].base),
149 (void *) PFN2ADDR(zones.info[i].count));
150 }
151
152 return (size_t) -1;
153 }
154 if (base < zones.info[i].base)
155 break;
156 }
157
158 /* Move other zones up */
159 for (size_t j = zones.count; j > i; j--)
160 zones.info[j] = zones.info[j - 1];
161
162 zones.count++;
163
164 return i;
165}
166
167/** Get total available frames.
168 *
169 * Assume interrupts are disabled and zones lock is
170 * locked.
171 *
172 * @return Total number of available frames.
173 *
174 */
175NO_TRACE static size_t frame_total_free_get_internal(void)
176{
177 size_t total = 0;
178 size_t i;
179
180 for (i = 0; i < zones.count; i++)
181 total += zones.info[i].free_count;
182
183 return total;
184}
185
186NO_TRACE size_t frame_total_free_get(void)
187{
188 size_t total;
189
190 irq_spinlock_lock(&zones.lock, true);
191 total = frame_total_free_get_internal();
192 irq_spinlock_unlock(&zones.lock, true);
193
194 return total;
195}
196
197
198/** Find a zone with a given frames.
199 *
200 * Assume interrupts are disabled and zones lock is
201 * locked.
202 *
203 * @param frame Frame number contained in zone.
204 * @param count Number of frames to look for.
205 * @param hint Used as zone hint.
206 *
207 * @return Zone index or -1 if not found.
208 *
209 */
210NO_TRACE size_t find_zone(pfn_t frame, size_t count, size_t hint)
211{
212 if (hint >= zones.count)
213 hint = 0;
214
215 size_t i = hint;
216 do {
217 if ((zones.info[i].base <= frame)
218 && (zones.info[i].base + zones.info[i].count >= frame + count))
219 return i;
220
221 i++;
222 if (i >= zones.count)
223 i = 0;
224
225 } while (i != hint);
226
227 return (size_t) -1;
228}
229
230/** @return True if zone can allocate specified number of frames */
231NO_TRACE static bool zone_can_alloc(zone_t *zone, size_t count,
232 pfn_t constraint)
233{
234 /*
235 * The function bitmap_allocate_range() does not modify
236 * the bitmap if the last argument is NULL.
237 */
238 return ((zone->flags & ZONE_AVAILABLE) &&
239 bitmap_allocate_range(&zone->bitmap, count, zone->base,
240 constraint, NULL));
241}
242
243/** Find a zone that can allocate specified number of frames
244 *
245 * Assume interrupts are disabled and zones lock is
246 * locked.
247 *
248 * @param count Number of free frames we are trying to find.
249 * @param flags Required flags of the target zone.
250 * @param constraint Indication of bits that cannot be set in the
251 * physical frame number of the first allocated frame.
252 * @param hind Preferred zone.
253 *
254 */
255NO_TRACE static size_t find_free_zone(size_t count, zone_flags_t flags,
256 pfn_t constraint, size_t hint)
257{
258 if (hint >= zones.count)
259 hint = 0;
260
261 size_t i = hint;
262 do {
263 /*
264 * Check whether the zone meets the search criteria.
265 */
266 if (ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) {
267 /*
268 * Check if the zone can satisfy the allocation request.
269 */
270 if (zone_can_alloc(&zones.info[i], count, constraint))
271 return i;
272 }
273
274 i++;
275 if (i >= zones.count)
276 i = 0;
277
278 } while (i != hint);
279
280 return (size_t) -1;
281}
282
283/******************/
284/* Zone functions */
285/******************/
286
287/** Return frame from zone. */
288NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t index)
289{
290 ASSERT(index < zone->count);
291
292 return &zone->frames[index];
293}
294
295/** Allocate frame in particular zone.
296 *
297 * Assume zone is locked and is available for allocation.
298 * Panics if allocation is impossible.
299 *
300 * @param zone Zone to allocate from.
301 * @param count Number of frames to allocate
302 * @param constraint Indication of bits that cannot be set in the
303 * physical frame number of the first allocated frame.
304 *
305 * @return Frame index in zone.
306 *
307 */
308NO_TRACE static size_t zone_frame_alloc(zone_t *zone, size_t count,
309 pfn_t constraint)
310{
311 ASSERT(zone->flags & ZONE_AVAILABLE);
312
313 /* Allocate frames from zone */
314 size_t index;
315 int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base,
316 constraint, &index);
317
318 ASSERT(avail);
319
320 /* Update frame reference count */
321 for (size_t i = 0; i < count; i++) {
322 frame_t *frame = zone_get_frame(zone, index + i);
323
324 ASSERT(frame->refcount == 0);
325 frame->refcount = 1;
326 }
327
328 /* Update zone information. */
329 zone->free_count -= count;
330 zone->busy_count += count;
331
332 return index;
333}
334
335/** Free frame from zone.
336 *
337 * Assume zone is locked and is available for deallocation.
338 *
339 * @param zone Pointer to zone from which the frame is to be freed.
340 * @param index Frame index relative to zone.
341 *
342 * @return Number of freed frames.
343 *
344 */
345NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t index)
346{
347 ASSERT(zone->flags & ZONE_AVAILABLE);
348
349 frame_t *frame = zone_get_frame(zone, index);
350
351 ASSERT(frame->refcount > 0);
352
353 if (!--frame->refcount) {
354 bitmap_free_range(&zone->bitmap, index, 1);
355
356 /* Update zone information. */
357 zone->free_count++;
358 zone->busy_count--;
359
360 return 1;
361 }
362
363 return 0;
364}
365
366/** Mark frame in zone unavailable to allocation. */
367NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t index)
368{
369 if (!(zone->flags & ZONE_AVAILABLE))
370 return;
371
372 frame_t *frame = zone_get_frame(zone, index);
373 if (frame->refcount > 0)
374 return;
375
376 frame->refcount = 1;
377 bitmap_set_range(&zone->bitmap, index, 1);
378
379 zone->free_count--;
380 reserve_force_alloc(1);
381}
382
383/** Merge two zones.
384 *
385 * Assume z1 & z2 are locked and compatible and zones lock is
386 * locked.
387 *
388 * @param z1 First zone to merge.
389 * @param z2 Second zone to merge.
390 * @param old_z1 Original data of the first zone.
391 * @param confdata Merged zone configuration data.
392 *
393 */
394NO_TRACE static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1,
395 void *confdata)
396{
397 ASSERT(zones.info[z1].flags & ZONE_AVAILABLE);
398 ASSERT(zones.info[z2].flags & ZONE_AVAILABLE);
399 ASSERT(zones.info[z1].flags == zones.info[z2].flags);
400 ASSERT(zones.info[z1].base < zones.info[z2].base);
401 ASSERT(!overlaps(zones.info[z1].base, zones.info[z1].count,
402 zones.info[z2].base, zones.info[z2].count));
403
404 /* Difference between zone bases */
405 pfn_t base_diff = zones.info[z2].base - zones.info[z1].base;
406
407 zones.info[z1].count = base_diff + zones.info[z2].count;
408 zones.info[z1].free_count += zones.info[z2].free_count;
409 zones.info[z1].busy_count += zones.info[z2].busy_count;
410
411 bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count,
412 BITMAP_BLOCK_SIZE, confdata +
413 (sizeof(frame_t) * zones.info[z1].count));
414 bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count);
415
416 zones.info[z1].frames = (frame_t *) confdata;
417
418 /*
419 * Copy frames and bits from both zones to preserve parents, etc.
420 */
421
422 for (size_t i = 0; i < old_z1->count; i++) {
423 bitmap_set(&zones.info[z1].bitmap, i,
424 bitmap_get(&old_z1->bitmap, i));
425 zones.info[z1].frames[i] = old_z1->frames[i];
426 }
427
428 for (size_t i = 0; i < zones.info[z2].count; i++) {
429 bitmap_set(&zones.info[z1].bitmap, base_diff + i,
430 bitmap_get(&zones.info[z2].bitmap, i));
431 zones.info[z1].frames[base_diff + i] =
432 zones.info[z2].frames[i];
433 }
434}
435
436/** Return old configuration frames into the zone.
437 *
438 * We have two cases:
439 * - The configuration data is outside the zone
440 * -> do nothing (perhaps call frame_free?)
441 * - The configuration data was created by zone_create
442 * or updated by reduce_region -> free every frame
443 *
444 * @param znum The actual zone where freeing should occur.
445 * @param pfn Old zone configuration frame.
446 * @param count Old zone frame count.
447 *
448 */
449NO_TRACE static void return_config_frames(size_t znum, pfn_t pfn, size_t count)
450{
451 ASSERT(zones.info[znum].flags & ZONE_AVAILABLE);
452
453 size_t cframes = SIZE2FRAMES(zone_conf_size(count));
454
455 if ((pfn < zones.info[znum].base) ||
456 (pfn >= zones.info[znum].base + zones.info[znum].count))
457 return;
458
459 for (size_t i = 0; i < cframes; i++)
460 (void) zone_frame_free(&zones.info[znum],
461 pfn - zones.info[znum].base + i);
462}
463
464/** Merge zones z1 and z2.
465 *
466 * The merged zones must be 2 zones with no zone existing in between
467 * (which means that z2 = z1 + 1). Both zones must be available zones
468 * with the same flags.
469 *
470 * When you create a new zone, the frame allocator configuration does
471 * not to be 2^order size. Once the allocator is running it is no longer
472 * possible, merged configuration data occupies more space :-/
473 *
474 */
475bool zone_merge(size_t z1, size_t z2)
476{
477 irq_spinlock_lock(&zones.lock, true);
478
479 bool ret = true;
480
481 /*
482 * We can join only 2 zones with none existing inbetween,
483 * the zones have to be available and with the same
484 * set of flags
485 */
486 if ((z1 >= zones.count) || (z2 >= zones.count) || (z2 - z1 != 1) ||
487 (zones.info[z1].flags != zones.info[z2].flags)) {
488 ret = false;
489 goto errout;
490 }
491
492 pfn_t cframes = SIZE2FRAMES(zone_conf_size(
493 zones.info[z2].base - zones.info[z1].base
494 + zones.info[z2].count));
495
496 /* Allocate merged zone data inside one of the zones */
497 pfn_t pfn;
498 if (zone_can_alloc(&zones.info[z1], cframes, 0)) {
499 pfn = zones.info[z1].base +
500 zone_frame_alloc(&zones.info[z1], cframes, 0);
501 } else if (zone_can_alloc(&zones.info[z2], cframes, 0)) {
502 pfn = zones.info[z2].base +
503 zone_frame_alloc(&zones.info[z2], cframes, 0);
504 } else {
505 ret = false;
506 goto errout;
507 }
508
509 /* Preserve original data from z1 */
510 zone_t old_z1 = zones.info[z1];
511
512 /* Do zone merging */
513 zone_merge_internal(z1, z2, &old_z1, (void *) PA2KA(PFN2ADDR(pfn)));
514
515 /* Subtract zone information from busy frames */
516 zones.info[z1].busy_count -= cframes;
517
518 /* Free old zone information */
519 return_config_frames(z1,
520 ADDR2PFN(KA2PA((uintptr_t) old_z1.frames)), old_z1.count);
521 return_config_frames(z1,
522 ADDR2PFN(KA2PA((uintptr_t) zones.info[z2].frames)),
523 zones.info[z2].count);
524
525 /* Move zones down */
526 for (size_t i = z2 + 1; i < zones.count; i++)
527 zones.info[i - 1] = zones.info[i];
528
529 zones.count--;
530
531errout:
532 irq_spinlock_unlock(&zones.lock, true);
533
534 return ret;
535}
536
537/** Merge all mergeable zones into one big zone.
538 *
539 * It is reasonable to do this on systems where
540 * BIOS reports parts in chunks, so that we could
541 * have 1 zone (it's faster).
542 *
543 */
544void zone_merge_all(void)
545{
546 size_t i = 1;
547
548 while (i < zones.count) {
549 if (!zone_merge(i - 1, i))
550 i++;
551 }
552}
553
554/** Create new frame zone.
555 *
556 * @param zone Zone to construct.
557 * @param start Physical address of the first frame within the zone.
558 * @param count Count of frames in zone.
559 * @param flags Zone flags.
560 * @param confdata Configuration data of the zone.
561 *
562 * @return Initialized zone.
563 *
564 */
565NO_TRACE static void zone_construct(zone_t *zone, pfn_t start, size_t count,
566 zone_flags_t flags, void *confdata)
567{
568 zone->base = start;
569 zone->count = count;
570 zone->flags = flags;
571 zone->free_count = count;
572 zone->busy_count = 0;
573
574 if (flags & ZONE_AVAILABLE) {
575 /*
576 * Initialize frame bitmap (located after the array of
577 * frame_t structures in the configuration space).
578 */
579
580 bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE,
581 confdata + (sizeof(frame_t) * count));
582 bitmap_clear_range(&zone->bitmap, 0, count);
583
584 /*
585 * Initialize the array of frame_t structures.
586 */
587
588 zone->frames = (frame_t *) confdata;
589
590 for (size_t i = 0; i < count; i++)
591 frame_initialize(&zone->frames[i]);
592 } else {
593 bitmap_initialize(&zone->bitmap, 0, 0, NULL);
594 zone->frames = NULL;
595 }
596}
597
598/** Compute configuration data size for zone.
599 *
600 * @param count Size of zone in frames.
601 *
602 * @return Size of zone configuration info (in bytes).
603 *
604 */
605size_t zone_conf_size(size_t count)
606{
607 return (count * sizeof(frame_t) +
608 bitmap_size(count, BITMAP_BLOCK_SIZE));
609}
610
611/** Allocate external configuration frames from low memory. */
612pfn_t zone_external_conf_alloc(size_t count)
613{
614 size_t frames = SIZE2FRAMES(zone_conf_size(count));
615
616 return ADDR2PFN((uintptr_t)
617 frame_alloc(frames, FRAME_LOWMEM | FRAME_ATOMIC, 0));
618}
619
620/** Create and add zone to system.
621 *
622 * @param start First frame number (absolute).
623 * @param count Size of zone in frames.
624 * @param confframe Where configuration frames are supposed to be.
625 * Automatically checks that we will not disturb the
626 * kernel and possibly init. If confframe is given
627 * _outside_ this zone, it is expected, that the area is
628 * already marked BUSY and big enough to contain
629 * zone_conf_size() amount of data. If the confframe is
630 * inside the area, the zone free frame information is
631 * modified not to include it.
632 *
633 * @return Zone number or -1 on error.
634 *
635 */
636size_t zone_create(pfn_t start, size_t count, pfn_t confframe,
637 zone_flags_t flags)
638{
639 irq_spinlock_lock(&zones.lock, true);
640
641 if (flags & ZONE_AVAILABLE) { /* Create available zone */
642 /*
643 * Theoretically we could have NULL here, practically make sure
644 * nobody tries to do that. If some platform requires, remove
645 * the assert
646 */
647 ASSERT(confframe != ADDR2PFN((uintptr_t ) NULL));
648
649 /* Update the known end of physical memory. */
650 config.physmem_end = max(config.physmem_end, PFN2ADDR(start + count));
651
652 /*
653 * If confframe is supposed to be inside our zone, then make sure
654 * it does not span kernel & init
655 */
656 size_t confcount = SIZE2FRAMES(zone_conf_size(count));
657
658 if ((confframe >= start) && (confframe < start + count)) {
659 for (; confframe < start + count; confframe++) {
660 uintptr_t addr = PFN2ADDR(confframe);
661 if (overlaps(addr, PFN2ADDR(confcount),
662 KA2PA(config.base), config.kernel_size))
663 continue;
664
665 if (overlaps(addr, PFN2ADDR(confcount),
666 KA2PA(config.stack_base), config.stack_size))
667 continue;
668
669 bool overlap = false;
670 for (size_t i = 0; i < init.cnt; i++) {
671 if (overlaps(addr, PFN2ADDR(confcount),
672 init.tasks[i].paddr,
673 init.tasks[i].size)) {
674 overlap = true;
675 break;
676 }
677 }
678
679 if (overlap)
680 continue;
681
682 break;
683 }
684
685 if (confframe >= start + count)
686 panic("Cannot find configuration data for zone.");
687 }
688
689 size_t znum = zones_insert_zone(start, count, flags);
690 if (znum == (size_t) -1) {
691 irq_spinlock_unlock(&zones.lock, true);
692 return (size_t) -1;
693 }
694
695 void *confdata = (void *) PA2KA(PFN2ADDR(confframe));
696 zone_construct(&zones.info[znum], start, count, flags, confdata);
697
698 /* If confdata in zone, mark as unavailable */
699 if ((confframe >= start) && (confframe < start + count)) {
700 for (size_t i = confframe; i < confframe + confcount; i++)
701 zone_mark_unavailable(&zones.info[znum],
702 i - zones.info[znum].base);
703 }
704
705 irq_spinlock_unlock(&zones.lock, true);
706
707 return znum;
708 }
709
710 /* Non-available zone */
711 size_t znum = zones_insert_zone(start, count, flags);
712 if (znum == (size_t) -1) {
713 irq_spinlock_unlock(&zones.lock, true);
714 return (size_t) -1;
715 }
716
717 zone_construct(&zones.info[znum], start, count, flags, NULL);
718
719 irq_spinlock_unlock(&zones.lock, true);
720
721 return znum;
722}
723
724/*******************/
725/* Frame functions */
726/*******************/
727
728/** Set parent of frame. */
729void frame_set_parent(pfn_t pfn, void *data, size_t hint)
730{
731 irq_spinlock_lock(&zones.lock, true);
732
733 size_t znum = find_zone(pfn, 1, hint);
734
735 ASSERT(znum != (size_t) -1);
736
737 zone_get_frame(&zones.info[znum],
738 pfn - zones.info[znum].base)->parent = data;
739
740 irq_spinlock_unlock(&zones.lock, true);
741}
742
743void *frame_get_parent(pfn_t pfn, size_t hint)
744{
745 irq_spinlock_lock(&zones.lock, true);
746
747 size_t znum = find_zone(pfn, 1, hint);
748
749 ASSERT(znum != (size_t) -1);
750
751 void *res = zone_get_frame(&zones.info[znum],
752 pfn - zones.info[znum].base)->parent;
753
754 irq_spinlock_unlock(&zones.lock, true);
755
756 return res;
757}
758
759/** Allocate frames of physical memory.
760 *
761 * @param count Number of continuous frames to allocate.
762 * @param flags Flags for host zone selection and address processing.
763 * @param constraint Indication of physical address bits that cannot be
764 * set in the address of the first allocated frame.
765 * @param pzone Preferred zone.
766 *
767 * @return Physical address of the allocated frame.
768 *
769 */
770uintptr_t frame_alloc_generic(size_t count, frame_flags_t flags,
771 uintptr_t constraint, size_t *pzone)
772{
773 ASSERT(count > 0);
774
775 size_t hint = pzone ? (*pzone) : 0;
776 pfn_t frame_constraint = ADDR2PFN(constraint);
777
778 /*
779 * If not told otherwise, we must first reserve the memory.
780 */
781 if (!(flags & FRAME_NO_RESERVE))
782 reserve_force_alloc(count);
783
784loop:
785 irq_spinlock_lock(&zones.lock, true);
786
787 /*
788 * First, find suitable frame zone.
789 */
790 size_t znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
791 frame_constraint, hint);
792
793 /*
794 * If no memory, reclaim some slab memory,
795 * if it does not help, reclaim all.
796 */
797 if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
798 irq_spinlock_unlock(&zones.lock, true);
799 size_t freed = slab_reclaim(0);
800 irq_spinlock_lock(&zones.lock, true);
801
802 if (freed > 0)
803 znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
804 frame_constraint, hint);
805
806 if (znum == (size_t) -1) {
807 irq_spinlock_unlock(&zones.lock, true);
808 freed = slab_reclaim(SLAB_RECLAIM_ALL);
809 irq_spinlock_lock(&zones.lock, true);
810
811 if (freed > 0)
812 znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
813 frame_constraint, hint);
814 }
815 }
816
817 if (znum == (size_t) -1) {
818 if (flags & FRAME_ATOMIC) {
819 irq_spinlock_unlock(&zones.lock, true);
820
821 if (!(flags & FRAME_NO_RESERVE))
822 reserve_free(count);
823
824 return 0;
825 }
826
827#ifdef CONFIG_DEBUG
828 size_t avail = frame_total_free_get_internal();
829#endif
830
831 irq_spinlock_unlock(&zones.lock, true);
832
833 if (!THREAD)
834 panic("Cannot wait for %zu frames to become available "
835 "(%zu available).", count, avail);
836
837 /*
838 * Sleep until some frames are available again.
839 */
840
841#ifdef CONFIG_DEBUG
842 printf("Thread %" PRIu64 " waiting for %zu frames "
843 "(%zu available).\n", THREAD->tid, count, avail);
844#endif
845
846 /*
847 * Since the mem_avail_mtx is an active mutex, we need to
848 * disable interrupts to prevent deadlock with TLB shootdown.
849 */
850 ipl_t ipl = interrupts_disable();
851 mutex_lock(&mem_avail_mtx);
852
853 if (mem_avail_req > 0)
854 mem_avail_req = min(mem_avail_req, count);
855 else
856 mem_avail_req = count;
857
858 size_t gen = mem_avail_gen;
859
860 while (gen == mem_avail_gen)
861 condvar_wait(&mem_avail_cv, &mem_avail_mtx);
862
863 mutex_unlock(&mem_avail_mtx);
864 interrupts_restore(ipl);
865
866#ifdef CONFIG_DEBUG
867 printf("Thread %" PRIu64 " woken up.\n", THREAD->tid);
868#endif
869
870 goto loop;
871 }
872
873 pfn_t pfn = zone_frame_alloc(&zones.info[znum], count,
874 frame_constraint) + zones.info[znum].base;
875
876 irq_spinlock_unlock(&zones.lock, true);
877
878 if (pzone)
879 *pzone = znum;
880
881 return PFN2ADDR(pfn);
882}
883
884uintptr_t frame_alloc(size_t count, frame_flags_t flags, uintptr_t constraint)
885{
886 return frame_alloc_generic(count, flags, constraint, NULL);
887}
888
889uintptr_t frame_alloc_noreserve(size_t count, frame_flags_t flags,
890 uintptr_t constraint)
891{
892 return frame_alloc_generic(count, flags | FRAME_NO_RESERVE, constraint,
893 NULL);
894}
895
896/** Free frames of physical memory.
897 *
898 * Find respective frame structures for supplied physical frames.
899 * Decrement each frame reference count. If it drops to zero, mark
900 * the frames as available.
901 *
902 * @param start Physical Address of the first frame to be freed.
903 * @param count Number of frames to free.
904 * @param flags Flags to control memory reservation.
905 *
906 */
907void frame_free_generic(uintptr_t start, size_t count, frame_flags_t flags)
908{
909 size_t freed = 0;
910
911 irq_spinlock_lock(&zones.lock, true);
912
913 for (size_t i = 0; i < count; i++) {
914 /*
915 * First, find host frame zone for addr.
916 */
917 pfn_t pfn = ADDR2PFN(start) + i;
918 size_t znum = find_zone(pfn, 1, 0);
919
920 ASSERT(znum != (size_t) -1);
921
922 freed += zone_frame_free(&zones.info[znum],
923 pfn - zones.info[znum].base);
924 }
925
926 irq_spinlock_unlock(&zones.lock, true);
927
928 /*
929 * Signal that some memory has been freed.
930 * Since the mem_avail_mtx is an active mutex,
931 * we need to disable interruptsto prevent deadlock
932 * with TLB shootdown.
933 */
934
935 ipl_t ipl = interrupts_disable();
936 mutex_lock(&mem_avail_mtx);
937
938 if (mem_avail_req > 0)
939 mem_avail_req -= min(mem_avail_req, freed);
940
941 if (mem_avail_req == 0) {
942 mem_avail_gen++;
943 condvar_broadcast(&mem_avail_cv);
944 }
945
946 mutex_unlock(&mem_avail_mtx);
947 interrupts_restore(ipl);
948
949 if (!(flags & FRAME_NO_RESERVE))
950 reserve_free(freed);
951}
952
953void frame_free(uintptr_t frame, size_t count)
954{
955 frame_free_generic(frame, count, 0);
956}
957
958void frame_free_noreserve(uintptr_t frame, size_t count)
959{
960 frame_free_generic(frame, count, FRAME_NO_RESERVE);
961}
962
963/** Add reference to frame.
964 *
965 * Find respective frame structure for supplied PFN and
966 * increment frame reference count.
967 *
968 * @param pfn Frame number of the frame to be freed.
969 *
970 */
971NO_TRACE void frame_reference_add(pfn_t pfn)
972{
973 irq_spinlock_lock(&zones.lock, true);
974
975 /*
976 * First, find host frame zone for addr.
977 */
978 size_t znum = find_zone(pfn, 1, 0);
979
980 ASSERT(znum != (size_t) -1);
981
982 zones.info[znum].frames[pfn - zones.info[znum].base].refcount++;
983
984 irq_spinlock_unlock(&zones.lock, true);
985}
986
987/** Mark given range unavailable in frame zones.
988 *
989 */
990NO_TRACE void frame_mark_unavailable(pfn_t start, size_t count)
991{
992 irq_spinlock_lock(&zones.lock, true);
993
994 for (size_t i = 0; i < count; i++) {
995 size_t znum = find_zone(start + i, 1, 0);
996
997 if (znum == (size_t) -1) /* PFN not found */
998 continue;
999
1000 zone_mark_unavailable(&zones.info[znum],
1001 start + i - zones.info[znum].base);
1002 }
1003
1004 irq_spinlock_unlock(&zones.lock, true);
1005}
1006
1007/** Initialize physical memory management.
1008 *
1009 */
1010void frame_init(void)
1011{
1012 if (config.cpu_active == 1) {
1013 zones.count = 0;
1014 irq_spinlock_initialize(&zones.lock, "frame.zones.lock");
1015 mutex_initialize(&mem_avail_mtx, MUTEX_ACTIVE);
1016 condvar_initialize(&mem_avail_cv);
1017 }
1018
1019 /* Tell the architecture to create some memory */
1020 frame_low_arch_init();
1021
1022 if (config.cpu_active == 1) {
1023 frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
1024 SIZE2FRAMES(config.kernel_size));
1025 frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)),
1026 SIZE2FRAMES(config.stack_size));
1027
1028 for (size_t i = 0; i < init.cnt; i++)
1029 frame_mark_unavailable(ADDR2PFN(init.tasks[i].paddr),
1030 SIZE2FRAMES(init.tasks[i].size));
1031
1032 if (ballocs.size)
1033 frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)),
1034 SIZE2FRAMES(ballocs.size));
1035
1036 /*
1037 * Blacklist first frame, as allocating NULL would
1038 * fail in some places
1039 */
1040 frame_mark_unavailable(0, 1);
1041 }
1042
1043 frame_high_arch_init();
1044}
1045
1046/** Adjust bounds of physical memory region according to low/high memory split.
1047 *
1048 * @param low[in] If true, the adjustment is performed to make the region
1049 * fit in the low memory. Otherwise the adjustment is
1050 * performed to make the region fit in the high memory.
1051 * @param basep[inout] Pointer to a variable which contains the region's base
1052 * address and which may receive the adjusted base address.
1053 * @param sizep[inout] Pointer to a variable which contains the region's size
1054 * and which may receive the adjusted size.
1055 *
1056 * @return True if the region still exists even after the adjustment.
1057 * @return False otherwise.
1058 *
1059 */
1060bool frame_adjust_zone_bounds(bool low, uintptr_t *basep, size_t *sizep)
1061{
1062 uintptr_t limit = KA2PA(config.identity_base) + config.identity_size;
1063
1064 if (low) {
1065 if (*basep > limit)
1066 return false;
1067
1068 if (*basep + *sizep > limit)
1069 *sizep = limit - *basep;
1070 } else {
1071 if (*basep + *sizep <= limit)
1072 return false;
1073
1074 if (*basep <= limit) {
1075 *sizep -= limit - *basep;
1076 *basep = limit;
1077 }
1078 }
1079
1080 return true;
1081}
1082
1083/** Return total size of all zones.
1084 *
1085 */
1086uint64_t zones_total_size(void)
1087{
1088 irq_spinlock_lock(&zones.lock, true);
1089
1090 uint64_t total = 0;
1091
1092 for (size_t i = 0; i < zones.count; i++)
1093 total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1094
1095 irq_spinlock_unlock(&zones.lock, true);
1096
1097 return total;
1098}
1099
1100void zones_stats(uint64_t *total, uint64_t *unavail, uint64_t *busy,
1101 uint64_t *free)
1102{
1103 ASSERT(total != NULL);
1104 ASSERT(unavail != NULL);
1105 ASSERT(busy != NULL);
1106 ASSERT(free != NULL);
1107
1108 irq_spinlock_lock(&zones.lock, true);
1109
1110 *total = 0;
1111 *unavail = 0;
1112 *busy = 0;
1113 *free = 0;
1114
1115 for (size_t i = 0; i < zones.count; i++) {
1116 *total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1117
1118 if (zones.info[i].flags & ZONE_AVAILABLE) {
1119 *busy += (uint64_t) FRAMES2SIZE(zones.info[i].busy_count);
1120 *free += (uint64_t) FRAMES2SIZE(zones.info[i].free_count);
1121 } else
1122 *unavail += (uint64_t) FRAMES2SIZE(zones.info[i].count);
1123 }
1124
1125 irq_spinlock_unlock(&zones.lock, true);
1126}
1127
1128/** Prints list of zones.
1129 *
1130 */
1131void zones_print_list(void)
1132{
1133#ifdef __32_BITS__
1134 printf("[nr] [base addr] [frames ] [flags ] [free frames ] [busy frames ]\n");
1135#endif
1136
1137#ifdef __64_BITS__
1138 printf("[nr] [base address ] [frames ] [flags ] [free frames ] [busy frames ]\n");
1139#endif
1140
1141 /*
1142 * Because printing may require allocation of memory, we may not hold
1143 * the frame allocator locks when printing zone statistics. Therefore,
1144 * we simply gather the statistics under the protection of the locks and
1145 * print the statistics when the locks have been released.
1146 *
1147 * When someone adds/removes zones while we are printing the statistics,
1148 * we may end up with inaccurate output (e.g. a zone being skipped from
1149 * the listing).
1150 */
1151
1152 for (size_t i = 0;; i++) {
1153 irq_spinlock_lock(&zones.lock, true);
1154
1155 if (i >= zones.count) {
1156 irq_spinlock_unlock(&zones.lock, true);
1157 break;
1158 }
1159
1160 uintptr_t base = PFN2ADDR(zones.info[i].base);
1161 size_t count = zones.info[i].count;
1162 zone_flags_t flags = zones.info[i].flags;
1163 size_t free_count = zones.info[i].free_count;
1164 size_t busy_count = zones.info[i].busy_count;
1165
1166 irq_spinlock_unlock(&zones.lock, true);
1167
1168 bool available = ((flags & ZONE_AVAILABLE) != 0);
1169
1170 printf("%-4zu", i);
1171
1172#ifdef __32_BITS__
1173 printf(" %p", (void *) base);
1174#endif
1175
1176#ifdef __64_BITS__
1177 printf(" %p", (void *) base);
1178#endif
1179
1180 printf(" %12zu %c%c%c%c%c ", count,
1181 available ? 'A' : '-',
1182 (flags & ZONE_RESERVED) ? 'R' : '-',
1183 (flags & ZONE_FIRMWARE) ? 'F' : '-',
1184 (flags & ZONE_LOWMEM) ? 'L' : '-',
1185 (flags & ZONE_HIGHMEM) ? 'H' : '-');
1186
1187 if (available)
1188 printf("%14zu %14zu",
1189 free_count, busy_count);
1190
1191 printf("\n");
1192 }
1193}
1194
1195/** Prints zone details.
1196 *
1197 * @param num Zone base address or zone number.
1198 *
1199 */
1200void zone_print_one(size_t num)
1201{
1202 irq_spinlock_lock(&zones.lock, true);
1203 size_t znum = (size_t) -1;
1204
1205 for (size_t i = 0; i < zones.count; i++) {
1206 if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
1207 znum = i;
1208 break;
1209 }
1210 }
1211
1212 if (znum == (size_t) -1) {
1213 irq_spinlock_unlock(&zones.lock, true);
1214 printf("Zone not found.\n");
1215 return;
1216 }
1217
1218 uintptr_t base = PFN2ADDR(zones.info[znum].base);
1219 zone_flags_t flags = zones.info[znum].flags;
1220 size_t count = zones.info[znum].count;
1221 size_t free_count = zones.info[znum].free_count;
1222 size_t busy_count = zones.info[znum].busy_count;
1223
1224 irq_spinlock_unlock(&zones.lock, true);
1225
1226 bool available = ((flags & ZONE_AVAILABLE) != 0);
1227
1228 uint64_t size;
1229 const char *size_suffix;
1230 bin_order_suffix(FRAMES2SIZE(count), &size, &size_suffix, false);
1231
1232 printf("Zone number: %zu\n", znum);
1233 printf("Zone base address: %p\n", (void *) base);
1234 printf("Zone size: %zu frames (%" PRIu64 " %s)\n", count,
1235 size, size_suffix);
1236 printf("Zone flags: %c%c%c%c%c\n",
1237 available ? 'A' : '-',
1238 (flags & ZONE_RESERVED) ? 'R' : '-',
1239 (flags & ZONE_FIRMWARE) ? 'F' : '-',
1240 (flags & ZONE_LOWMEM) ? 'L' : '-',
1241 (flags & ZONE_HIGHMEM) ? 'H' : '-');
1242
1243 if (available) {
1244 bin_order_suffix(FRAMES2SIZE(busy_count), &size, &size_suffix,
1245 false);
1246 printf("Allocated space: %zu frames (%" PRIu64 " %s)\n",
1247 busy_count, size, size_suffix);
1248 bin_order_suffix(FRAMES2SIZE(free_count), &size, &size_suffix,
1249 false);
1250 printf("Available space: %zu frames (%" PRIu64 " %s)\n",
1251 free_count, size, size_suffix);
1252 }
1253}
1254
1255/** @}
1256 */
Note: See TracBrowser for help on using the repository browser.