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

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

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