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

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 566da7f8 was 566da7f8, checked in by Vojtech Horky <vojtechhorky@…>, 11 years ago

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