← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xen/utopic

« back to all changes in this revision

Viewing changes to tools/firmware/rombios/32bit/pmm.c

  • Committer: Bazaar Package Importer
  • Author(s): Bastian Blank
  • Date: 2010-05-06 15:47:38 UTC
  • mto: (1.3.1) (15.1.1 sid) (4.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20100506154738-agoz0rlafrh1fnq7
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/firmware/rombios/32bit/pmm.c
 
1
/*
 
2
 *  pmm.c - POST(Power On Self Test) Memory Manager
 
3
 *  according to the specification described in
 
4
 *  http://www.phoenix.com/NR/rdonlyres/873A00CF-33AC-4775-B77E-08E7B9754993/0/specspmm101.pdf
 
5
 *
 
6
 *  This library is free software; you can redistribute it and/or
 
7
 *  modify it under the terms of the GNU Lesser General Public
 
8
 *  License as published by the Free Software Foundation; either
 
9
 *  version 2 of the License, or (at your option) any later version.
 
10
 *
 
11
 *  This library is distributed in the hope that it will be useful,
 
12
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
14
 *  Lesser General Public License for more details.
 
15
 *
 
16
 *  You should have received a copy of the GNU Lesser General Public
 
17
 *  License along with this library; if not, write to the Free Software
 
18
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 
19
 *
 
20
 *  Copyright (C) 2009 FUJITSU LIMITED
 
21
 *
 
22
 *  Author: Kouya Shimura <kouya@jp.fujitsu.com>
 
23
 */
 
24
 
 
25
/*
 
26
 * Algorithm:
 
27
 *
 
28
 * This is not a fast storage allocator but simple one.  There is no
 
29
 * segregated management by block size and it does nothing special for
 
30
 * avoiding the fragmentation.
 
31
 *
 
32
 * The allocation algorithm is a first-fit. All memory blocks are
 
33
 * managed by linear single linked list in order of the address.
 
34
 * (i.e. There is no backward pointer) It searches the first available
 
35
 * equal or larger block from the head (lowest address) of memory
 
36
 * heap. The larger block is splitted into two blocks unless one side
 
37
 * becomes too small.
 
38
 * 
 
39
 * For de-allocation, the specified block is just marked as available
 
40
 * and it does nothing else. Thus, the fragmentation will occur. The
 
41
 * collection of continuous available blocks are done on the search
 
42
 * phase of another block allocation.
 
43
 *
 
44
 * The following is an abstract of this algorithm. The actual code
 
45
 * looks complicated on account of alignment and checking the handle.
 
46
 *
 
47
 *     static memblk_t *
 
48
 *     alloc(heap_t *heap, uint32_t size)
 
49
 *     {
 
50
 *         static memblk_t *mb;
 
51
 *         for_each_memblk(heap, mb) // search memory blocks
 
52
 *             if (memblk_is_avail(mb))
 
53
 *             {
 
54
 *                 collect_avail_memblks(heap, mb);
 
55
 *                 if (size <= memblk_bufsize(mb))
 
56
 *                 {
 
57
 *                     split_memblk(mb, size);
 
58
 *                     set_inuse(mb);
 
59
 *                     return mb;
 
60
 *                 }
 
61
 *             }
 
62
 *         return NULL;
 
63
 *     }
 
64
 */
 
65
 
 
66
#include <stdint.h>
 
67
#include <stddef.h>
 
68
#include <../hvmloader/config.h>
 
69
#include <../hvmloader/e820.h>
 
70
#include "util.h"
 
71
 
 
72
#define DEBUG_PMM 0
 
73
 
 
74
#define __stringify(a) #a
 
75
#define stringify(a) __stringify(a)
 
76
 
 
77
#define ASSERT(_expr, _action)                                  \
 
78
    if (!(_expr)) {                                             \
 
79
        printf("ASSERTION FAIL: %s %s:%d %s()\n",               \
 
80
               stringify(_expr), __FILE__, __LINE__, __func__); \
 
81
        _action;                                                \
 
82
    } else
 
83
 
 
84
#if DEBUG_PMM
 
85
# define PMM_DEBUG(format, p...) printf("PMM " format, ##p)
 
86
#else
 
87
# define PMM_DEBUG(format, p...)
 
88
#endif
 
89
 
 
90
struct pmmAllocArgs {
 
91
    uint16_t function;
 
92
    uint32_t length;
 
93
    uint32_t handle;
 
94
    uint16_t flags;
 
95
} __attribute__ ((packed));
 
96
 
 
97
struct pmmFindArgs {
 
98
    uint16_t function;
 
99
    uint32_t handle;
 
100
} __attribute__ ((packed));
 
101
 
 
102
struct pmmDeallocateArgs {
 
103
    uint16_t function;
 
104
    uint32_t buffer;
 
105
} __attribute__ ((packed));
 
106
 
 
107
#define PMM_FUNCTION_ALLOCATE   0
 
108
#define PMM_FUNCTION_FIND       1         
 
109
#define PMM_FUNCTION_DEALLOC    2
 
110
 
 
111
#define PARAGRAPH_LENGTH        16  // unit of length
 
112
 
 
113
#define PMM_HANDLE_ANONYMOUS    0xffffffff
 
114
 
 
115
#define PMM_FLAGS_MEMORY_TYPE_MASK      0x0003
 
116
#define PMM_FLAGS_MEMORY_INVALID        0
 
117
#define PMM_FLAGS_MEMORY_CONVENTIONAL   1  // 0 to 1MB
 
118
#define PMM_FLAGS_MEMORY_EXTENDED       2  // 1MB to 4GB
 
119
#define PMM_FLAGS_MEMORY_ANY            3  // whichever is available
 
120
#define PMM_FLAGS_ALIGINMENT            0x0004
 
121
 
 
122
/* Error code */
 
123
#define PMM_ENOMEM      (0)     // Out of memory, duplicate handle
 
124
#define PMM_EINVAL      (-1)    // Invalid argument
 
125
 
 
126
#define ALIGN_UP(addr, size)    (((addr)+((size)-1))&(~((size)-1)))
 
127
#define ALIGN_DOWN(addr, size)  ((addr)&(~((size)-1)))
 
128
 
 
129
typedef struct memblk {
 
130
    uint32_t magic;      // inuse or available
 
131
    struct memblk *next; // points the very next of this memblk
 
132
    uint32_t handle;     // identifier of this block
 
133
    uint32_t __fill;     // for 16byte alignment, not used
 
134
    uint8_t buffer[0];
 
135
} memblk_t;
 
136
 
 
137
typedef struct heap {
 
138
    memblk_t *head;     // start address of heap
 
139
    memblk_t *end;      // end address of heap
 
140
} heap_t;
 
141
 
 
142
#define HEAP_NOT_INITIALIZED    (memblk_t *)-1
 
143
#define HEAP_ALIGNMENT          16
 
144
 
 
145
/*
 
146
 * PMM handles two memory heaps, the caller chooses either.
 
147
 *
 
148
 * - conventional memroy (below 1MB)
 
149
 *    In HVM, the area is fixed. 0x00010000-0x0007FFFF
 
150
 *    (from SCRATCH_PHYSICAL_ADDRESS to HYPERCALL_PHYSICAL_ADDRESS)
 
151
 *
 
152
 * - extended memory (start at 1MB, below 4GB)
 
153
 *    In HVM, the area starts at memory address 0x00100000.
 
154
 *    The end address is variable. We read low RAM address from e820 table.
 
155
 *
 
156
 * The following struct must be located in the data segment since bss
 
157
 * in 32bitbios doesn't be relocated.
 
158
 */
 
159
static struct {
 
160
    heap_t heap;     // conventional memory
 
161
    heap_t ext_heap; // extended memory
 
162
} pmm_data = { {HEAP_NOT_INITIALIZED, NULL}, {NULL, NULL} };
 
163
 
 
164
/* These values are private use, not a spec in PMM */
 
165
#define MEMBLK_MAGIC_INUSE   0x2A4D4D50  // 'PMM*'
 
166
#define MEMBLK_MAGIC_AVAIL   0x5F4D4D50  // 'PMM_'
 
167
 
 
168
#define memblk_is_inuse(_mb)  ((_mb)->magic == MEMBLK_MAGIC_INUSE)
 
169
#define memblk_is_avail(_mb)  ((_mb)->magic == MEMBLK_MAGIC_AVAIL)
 
170
 
 
171
static void set_inuse(memblk_t *mb, uint32_t handle)
 
172
{
 
173
    mb->magic = MEMBLK_MAGIC_INUSE;
 
174
    mb->handle = handle;
 
175
}
 
176
 
 
177
static void set_avail(memblk_t *mb)
 
178
{
 
179
    mb->magic = MEMBLK_MAGIC_AVAIL;
 
180
    mb->handle = PMM_HANDLE_ANONYMOUS;
 
181
}
 
182
 
 
183
#define MEMBLK_HEADER_SIZE   ((int)(&((memblk_t *)0)->buffer))
 
184
#define MIN_MEMBLK_SIZE      (MEMBLK_HEADER_SIZE + PARAGRAPH_LENGTH)
 
185
 
 
186
#define memblk_size(_mb)     ((void *)((_mb)->next) - (void *)(_mb))
 
187
#define memblk_buffer(_mb)   ((uint32_t)(&(_mb)->buffer))
 
188
#define memblk_bufsize(_mb)  (memblk_size(_mb) - MEMBLK_HEADER_SIZE)
 
189
 
 
190
#define buffer_memblk(_buf)  (memblk_t *)((_buf) - MEMBLK_HEADER_SIZE)
 
191
 
 
192
#define memblk_loop_mbondition(_h, _mb) \
 
193
    (((_mb) < (_h)->end) && (/* avoid infinite loop */ (_mb) < (_mb)->next))
 
194
 
 
195
#define for_each_memblk(_h, _mb)                \
 
196
    for ((_mb) = (_h)->head;                    \
 
197
         memblk_loop_mbondition(_h, _mb);       \
 
198
         (_mb) = (_mb)->next)
 
199
 
 
200
#define for_remain_memblk(_h, _mb)              \
 
201
    for (;                                      \
 
202
         memblk_loop_mbondition(_h, _mb);       \
 
203
         (_mb) = (_mb)->next)
 
204
 
 
205
/*
 
206
 *                                       <-size->
 
207
 *    +==================+======+       +========+========+======+
 
208
 *    |      avail       |      |       | avail  | avail  |      |
 
209
 *    |      memblk      |memblk|...    | memblk | memblk |memblk|...
 
210
 *    +==================+======+   =>  +========+========+======+
 
211
 *    ^ |                ^ |    ^         |      ^ |      ^ |    ^
 
212
 *    | |next            | |next|         |next  | |next  | |next|
 
213
 *    | \________________/ \____/         \______/ \______/ \____/
 
214
 *    |                                          ^
 
215
 *    |                                          |
 
216
 *    mb                                         +- sb(return value)
 
217
 */
 
218
static memblk_t *
 
219
split_memblk(memblk_t *mb, uint32_t size)
 
220
{
 
221
    memblk_t *sb = (void *)memblk_buffer(mb) + size;
 
222
 
 
223
    /* Only split if the remaining fragment is big enough. */
 
224
    if ( (memblk_bufsize(mb) - size) < MIN_MEMBLK_SIZE)
 
225
        return mb;
 
226
 
 
227
    sb->next = mb->next;
 
228
    set_avail(sb);
 
229
 
 
230
    mb->next = sb;
 
231
    return sb;
 
232
}
 
233
 
 
234
/*
 
235
 *    +======+======+======+======+       +=================+======+
 
236
 *    |avail |avail |avail |inuse |       |      avail      |inuse |   
 
237
 *    |memblk|memblk|memblk|memblk|...    |      memblk     |memblk|...
 
238
 *    +======+======+======+======+   =>  +=================+======+
 
239
 *    ^ |    ^ |    ^ |    ^ |    ^         |               ^ |    ^
 
240
 *    | |next| |next| |next| |next|         |next           | |next|
 
241
 *    | \____/ \____/ \____/ \____/         \_______________/ \____/
 
242
 *    |
 
243
 *    mb
 
244
 */
 
245
static void
 
246
collect_avail_memblks(heap_t *heap, memblk_t *mb)
 
247
{
 
248
    memblk_t *nb = mb->next;
 
249
 
 
250
    for_remain_memblk ( heap, nb )
 
251
        if ( memblk_is_inuse(nb) )
 
252
            break;
 
253
    mb->next = nb;
 
254
}
 
255
 
 
256
static void
 
257
pmm_init_heap(heap_t *heap, uint32_t from_addr, uint32_t to_addr)
 
258
{
 
259
    memblk_t *mb = (memblk_t *)ALIGN_UP(from_addr, HEAP_ALIGNMENT);
 
260
 
 
261
    mb->next = (memblk_t *)ALIGN_DOWN(to_addr, HEAP_ALIGNMENT);
 
262
    set_avail(mb);
 
263
 
 
264
    heap->head = mb;
 
265
    heap->end = mb->next;
 
266
}
 
267
 
 
268
static void
 
269
pmm_initalize(void)
 
270
{
 
271
    int i, e820_nr = *E820_NR;
 
272
    struct e820entry *e820 = E820;
 
273
 
 
274
    /* Extended memory: RAM below 4GB, 0x100000-0xXXXXXXXX */
 
275
    for ( i = 0; i < e820_nr; i++ )
 
276
    {
 
277
        if ( (e820[i].type == E820_RAM) && (e820[i].addr >= 0x00100000) )
 
278
        {
 
279
            pmm_init_heap(&pmm_data.ext_heap, e820[i].addr, 
 
280
                          e820[i].addr + e820[i].size);
 
281
            break;
 
282
        }
 
283
    }
 
284
 
 
285
    /* convectional memory: RAM below 1MB, 0x10000-0x7FFFF */
 
286
    pmm_init_heap(&pmm_data.heap, SCRATCH_PHYSICAL_ADDRESS,
 
287
                  HYPERCALL_PHYSICAL_ADDRESS);
 
288
}
 
289
 
 
290
static uint32_t
 
291
pmm_max_avail_length(heap_t *heap)
 
292
{
 
293
    memblk_t *mb;
 
294
    uint32_t size, max = 0;
 
295
 
 
296
    for_each_memblk ( heap, mb )
 
297
    {
 
298
        if ( !memblk_is_avail(mb) )
 
299
            continue;
 
300
        collect_avail_memblks(heap, mb);
 
301
        size = memblk_bufsize(mb);
 
302
        if ( size > max )
 
303
            max = size;
 
304
    }
 
305
 
 
306
    return (max / PARAGRAPH_LENGTH);
 
307
}
 
308
 
 
309
static memblk_t *
 
310
first_fit(heap_t *heap, uint32_t size, uint32_t handle, uint32_t flags)
 
311
{
 
312
    memblk_t *mb;
 
313
    int32_t align = 0;
 
314
 
 
315
    if ( flags & PMM_FLAGS_ALIGINMENT )
 
316
        align = ((size ^ (size - 1)) >> 1) + 1;
 
317
 
 
318
    for_each_memblk ( heap, mb )
 
319
    {
 
320
        if ( memblk_is_avail(mb) )
 
321
        {
 
322
            collect_avail_memblks(heap, mb);
 
323
 
 
324
            if ( align )
 
325
            {
 
326
                uint32_t addr = memblk_buffer(mb);
 
327
                uint32_t offset = ALIGN_UP(addr, align) - addr;
 
328
 
 
329
                if ( offset > 0 )
 
330
                {
 
331
                    ASSERT(offset >= MEMBLK_HEADER_SIZE, continue);
 
332
 
 
333
                    if ( (offset + size) > memblk_bufsize(mb) )
 
334
                        continue;
 
335
 
 
336
                    mb = split_memblk(mb, offset - MEMBLK_HEADER_SIZE);
 
337
                    return mb;
 
338
                }
 
339
            }
 
340
 
 
341
            if ( size <= memblk_bufsize(mb) )
 
342
                return mb;
 
343
        }
 
344
        else
 
345
        {
 
346
            ASSERT(memblk_is_inuse(mb), return NULL);
 
347
 
 
348
            /* Duplication check for handle. */
 
349
            if ( (handle != PMM_HANDLE_ANONYMOUS) && (mb->handle == handle) )
 
350
                return NULL;
 
351
        }
 
352
    }
 
353
 
 
354
    return NULL;
 
355
}
 
356
 
 
357
static memblk_t *
 
358
pmm_find_handle(heap_t *heap, uint32_t handle)
 
359
{
 
360
    memblk_t *mb;
 
361
 
 
362
    if ( handle == PMM_HANDLE_ANONYMOUS )
 
363
        return NULL;
 
364
 
 
365
    for_each_memblk ( heap, mb )
 
366
        if ( mb->handle == handle )
 
367
            return mb;
 
368
 
 
369
    return NULL;
 
370
}
 
371
 
 
372
/*
 
373
 * allocate a memory block of the specified type and size, and returns
 
374
 * the address of the memory block.
 
375
 *
 
376
 * A client-specified identifier to be associated with the allocated
 
377
 * memory block. A handle of 0xFFFFFFFF indicates that no identifier
 
378
 * should be associated with the block. Such a memory block is known
 
379
 * as an "anonymous" memory block and cannot be found using the
 
380
 * pmmFind function. If a specified handle for a requested memory
 
381
 * block is already used in a currently allocated memory block, the
 
382
 * error value of 0x00000000 is returned
 
383
 *
 
384
 * If length is 0x00000000, no memory is allocated and the value
 
385
 * returned is the size of the largest memory block available for the
 
386
 * memory type specified in the flags parameter. The alignment bit in
 
387
 * the flags register is ignored when calculating the largest memory
 
388
 * block available.
 
389
 *
 
390
 * If a specified handle for a requested memory block is already used
 
391
 * in a currently allocated memory block, the error value of
 
392
 * 0x00000000 is returned.
 
393
 * 
 
394
 * A return value of 0x00000000 indicates that an error occurred and
 
395
 * no memory has been allocated. 
 
396
 */
 
397
static uint32_t
 
398
pmmAllocate(uint32_t length, uint32_t handle, uint16_t flags)
 
399
{
 
400
    heap_t *heap;
 
401
    memblk_t *mb;
 
402
    uint32_t size;
 
403
 
 
404
    switch ( flags & PMM_FLAGS_MEMORY_TYPE_MASK )
 
405
    {
 
406
    case PMM_FLAGS_MEMORY_CONVENTIONAL:
 
407
        heap = &pmm_data.heap;
 
408
        break;
 
409
 
 
410
    case PMM_FLAGS_MEMORY_EXTENDED:
 
411
    case PMM_FLAGS_MEMORY_ANY: /* XXX: ignore conventional memory for now */
 
412
        heap = &pmm_data.ext_heap;
 
413
        break;
 
414
 
 
415
    default:
 
416
        return PMM_EINVAL;
 
417
    }
 
418
 
 
419
    /* return the largest memory block available */
 
420
    if ( length == 0 )
 
421
        return pmm_max_avail_length(heap);
 
422
 
 
423
    size = length * PARAGRAPH_LENGTH;
 
424
    mb = first_fit(heap, size, handle, flags);
 
425
 
 
426
    if ( mb == NULL )
 
427
        return PMM_ENOMEM;
 
428
 
 
429
    /* duplication check for handle */
 
430
    if ( handle != PMM_HANDLE_ANONYMOUS )
 
431
    {
 
432
        memblk_t *nb = mb->next;
 
433
 
 
434
        for_remain_memblk(heap, nb)
 
435
            if (nb->handle == handle)
 
436
                return PMM_ENOMEM;
 
437
    }
 
438
 
 
439
    split_memblk(mb, size);
 
440
    set_inuse(mb, handle);
 
441
 
 
442
    return memblk_buffer(mb);
 
443
}
 
444
 
 
445
/*
 
446
 * returns the address of the memory block associated with the
 
447
 * specified handle.  
 
448
 *
 
449
 * A return value of 0x00000000 indicates that the handle does not
 
450
 * correspond to a currently allocated memory block.
 
451
 */
 
452
static uint32_t
 
453
pmmFind(uint32_t handle)
 
454
{
 
455
    memblk_t *mb;
 
456
 
 
457
    if ( handle == PMM_HANDLE_ANONYMOUS )
 
458
        return 0;
 
459
 
 
460
    mb = pmm_find_handle(&pmm_data.heap, handle);
 
461
    if ( mb == NULL )
 
462
        mb = pmm_find_handle(&pmm_data.ext_heap, handle);
 
463
 
 
464
    return mb ? memblk_buffer(mb) : 0;
 
465
}
 
466
 
 
467
/* 
 
468
 * frees the specified memory block that was previously allocated by
 
469
 * pmmAllocate.
 
470
 *
 
471
 * If the memory block was deallocated correctly, the return value is
 
472
 * 0x00000000. If there was an error, the return value is non-zero.
 
473
 */
 
474
static uint32_t
 
475
pmmDeallocate(uint32_t buffer)
 
476
{
 
477
    memblk_t *mb = buffer_memblk(buffer);
 
478
 
 
479
    if ( !memblk_is_inuse(mb) )
 
480
        return PMM_EINVAL;
 
481
 
 
482
    set_avail(mb);
 
483
    return 0;
 
484
}
 
485
 
 
486
 
 
487
union pmm_args {
 
488
    uint16_t function;
 
489
    struct pmmAllocArgs alloc;
 
490
    struct pmmFindArgs find;
 
491
    struct pmmDeallocateArgs dealloc;
 
492
} __attribute__ ((packed));
 
493
 
 
494
/*
 
495
 * entry function of all PMM services.
 
496
 *
 
497
 * Values returned to the caller are placed in the DX:AX register
 
498
 * pair. The flags and all registers, other than DX and AX, are
 
499
 * preserved across calls to PMM services.
 
500
 */
 
501
uint32_t
 
502
pmm(void *argp)
 
503
{
 
504
    union pmm_args *ap = argp;
 
505
    uint32_t ret = PMM_EINVAL;
 
506
 
 
507
    if ( pmm_data.heap.head == HEAP_NOT_INITIALIZED )
 
508
        pmm_initalize();
 
509
 
 
510
    switch ( ap->function )
 
511
    {
 
512
    case PMM_FUNCTION_ALLOCATE:
 
513
        ret = pmmAllocate(ap->alloc.length, ap->alloc.handle, ap->alloc.flags);
 
514
        PMM_DEBUG("Alloc length=%x handle=%x flags=%x ret=%x\n", 
 
515
                  ap->alloc.length, ap->alloc.handle, ap->alloc.flags, ret);
 
516
        break;
 
517
 
 
518
    case PMM_FUNCTION_FIND:
 
519
        ret = pmmFind(ap->find.handle);
 
520
        PMM_DEBUG("Find handle=%x ret=%x\n", ap->find.handle, ret);
 
521
        break;
 
522
 
 
523
    case PMM_FUNCTION_DEALLOC:
 
524
        ret = pmmDeallocate(ap->dealloc.buffer);
 
525
        PMM_DEBUG("Dealloc buffer=%x ret=%x\n", ap->dealloc.buffer, ret);
 
526
        break;
 
527
 
 
528
    default:
 
529
        PMM_DEBUG("Invalid function:%d\n", ap->function);
 
530
        break;
 
531
    }
 
532
 
 
533
    return ret;
 
534
}