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

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since b1c57a8 was b1c57a8, checked in by Jakub Jermar <jakub@…>, 11 years ago

Merge from lp:~adam-hraska+lp/helenos/rcu/.

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