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

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 9306cd7 was 63e27ef, checked in by Jiri Svoboda <jiri@…>, 8 years ago

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