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

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

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