region.c
9.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
/**************************************************************************
* *
* Copyright (C) 1994, Silicon Graphics, Inc. *
* *
* These coded instructions, statements, and computer programs contain *
* unpublished proprietary information of Silicon Graphics, Inc., and *
* are protected by Federal copyright law. They may not be disclosed *
* to third parties or copied or duplicated in any form, in whole or *
* in part, without the prior written consent of Silicon Graphics, Inc. *
* *
**************************************************************************/
/**************************************************************************
*
* Module: region.c
*
* $Revision: 1.1.1.2 $
* $Date: 2002/10/29 08:06:43 $
* $Author: blythe $
* $Source: /root/leakn64/depot/rf/sw/n64os20l/libultra/monegi/rg/region.c,v $
*
* Description:
* This file contains routines to manage a region of contiguous
* memory by partitioning the memory area into equal-sized buffers
* and allowing user to malloc/free these buffers.
*
**************************************************************************/
#include "os.h"
#include "os_internal.h"
#include "region.h"
#include "ultraerror.h"
#include "assert.h"
/***************************************
Overview
--------
A region is a user-defined, physically contiguous block of memory,
divided into a set of equal-sized buffers.
The simple memory scheme discussed here is desgined to provide the
following features:
(a) dynamic creation of memory regions to contain
fixed sized buffers
(b) dynamic allocation/free of memory buffers within
the region
The goals for this scheme is to:
1. provide a small-and-yet-fast (with deterministic
alloc/free time) mechanism to allocate buffers from a
contiguous memory region
2. provide an efficient way for the user to optimize the
memory usage based on his application's requirements
Any number of memory regions can be created at run-time, using the
osCreateRegion() call. The user must supply a block of memory large
enough for the specified buffer size, including a certain overhead
for control structure.
This scheme takes a small portion at the beginning of the input
memory area to use as the region control header. The rest of the
region is organized simply as a pool of equal-sized buffers. The
buffer size is adjusted to be aligned to the input parameter
alignSize in osCreateRegion(). Currently, the alignment size can
range from 2 bytes (16 bits) to 16 bytes (128 bits).
The region control header structure consists of: starting address of
the first fixed size buffer, region ending address, buffer size,
number of buffer available in this region, an index to the first
free buffer in the free buffer list, and alignment size (in bytes).
The first 16-bit of each buffer is used as an index pointer to the
next free buffer. The index pointer of the last buffer in the free
list is set to BUF_FREE_WO_NEXT (or 8000H) which uses the
most-significant bit in the 16-bit half-word. Once a buffer is
malloced, its index pointer will be used for data.
Upon creation, each region is given a unique 32-bit region id. The
user uses this id to reference the region. Since the id is actually
the address of the control header for the region, any reference leads
directly to it, without any searching.
Two simple calls, osMalloc() and osFree(), provide fast,
dynamic allocation and de-allocation of buffers. No searching is
needed - osMalloc() takes the buffer at the head of the region's
free list, osFree() puts the buffer back at the head of the free
list.
A region has the following limits:
(1) it can only have up to 32,768 (15-bit) buffers
(2) the buffer address is automatically aligned to a
boundary according to the alignSize value (default
is 64-bit alignment)
(3) the buffer size is rounded up to the alignSize value
(default is a 64-bit boundary)
The user must take extreme caution to not create multiple regions
pointing to the same memory address. This will cause unexpected
behavior since this scheme does not perform any memory check during
region creation.
Data Structures
---------------
1. Region Header Structure
Start address to first buffer (32-bit)
End address of region (32-bit)
Buffer size (32-bit)
Total number of buffers in this region (16-bit)
Pointer to first available buffer (16-bit)
Alignment size in bytes (16-bit)
2. Region memory layout
SBA = Start of Buffer Address
n = Total number of buffers in region
8000H = Buffer free without next in list
----- +--------------------------+ Region start address
| |
H | Region Header |
| structure |
D | (Region) |
| |
R |..........................|
| freeList = 0 |
----- +--------------------------+ +Header (Start of Buffer) = SBA
| next free buffer = 1 |
|..........................|
| |
| Buffer #0 |
| |
D +--------------------------+ +SBA+(Buffer Size)
| next free buffer = 2 |
A |..........................|
| |
T | Buffer #1 |
| |
A +--------------------------+
| ... |
| |
+--------------------------+ +SBA+(Buffer Size*(n-1))
| next free buffer = 8000H |
|..........................|
| |
| Buffer #n-1 |
| |
----- +--------------------------+ +Length = Region end address
*/
/*
* Name: osCreateRegion
*
* Description:
* This routine sets up an area of contiguous memory defined as
* starting at virtual address 'startAddress' and extending for
* 'length' bytes. This memory area, or region, can later be used
* to malloc buffers of at-least size 'bufferSize'. 'alignSize' specifies
* the number of bytes used for aligning the buffer address as well as
* buffer size. It can range from 2 bytes (16 bits) to 16 bytes (128 bits).
* If 'alignSize' is 0, the default value (of 8 bytes) is used.
*
* Upon success, the routine returns a pointer (which is aligned to
* alignSize) to where the region starts. This pointer is used as a unique
* region identifier in osMalloc() and osFree() routines.
* osCreateRegion() returns a null pointer if one the of the following
* conditions is encountered: (1) null start address, (2) length or
* buffer size is less than 0, or (3) buffer size is greater than the
* actual length remained for storing data.
*
* Globals Referenced:
* None
*/
void *
osCreateRegion(void *startAddress, u32 length, u32 bufferSize, u32 alignSize)
{
register OSRegion *rp;
register int i;
register char *addr;
/* Check for non-empty starting addres */
assert(startAddress != (void *)NULL);
#ifdef _DEBUG
/* Check for valid alignment size */
if ((alignSize != 0) &&
(alignSize != OS_RG_ALIGN_2B) && (alignSize != OS_RG_ALIGN_4B) &&
(alignSize != OS_RG_ALIGN_8B) && (alignSize != OS_RG_ALIGN_16B)) {
__osError(ERR_OSCREATEREGION_ALIGN, 1, alignSize);
return(NULL);
}
#endif
if (alignSize == 0) {
alignSize = OS_RG_ALIGN_DEFAULT;
}
/* Align start address properly */
rp = (OSRegion *)ALIGN(startAddress, alignSize);
/* Adjust region length based on new alignment */
length -= ((char *)rp - (char *)startAddress);
/* Round off buffer size to proper alignment */
RP(bufferSize) = ALIGN(bufferSize, alignSize);
/* Calculate possible number of buffers in this region */
RP(bufferCount) = (long)(length-ALIGN(sizeof(OSRegion), alignSize)) /
RP(bufferSize);
#ifdef _DEBUG
/* Check to make sure that buffer size can fit within region */
if (RP(bufferCount) <= 0) {
__osError(ERR_OSCREATEREGION_SIZE, 2, length, bufferSize);
return(NULL) ;
}
#endif
/* If necessary, adjust bufferCount to MAX_BUFCOUNT */
if (RP(bufferCount) > MAX_BUFCOUNT) {
RP(bufferCount) = MAX_BUFCOUNT;
}
RP(startBufferAddress) = (char *)rp + ALIGN(sizeof(OSRegion), alignSize);
RP(endAddress) = (char *)rp + length;
/* Initialize the free list */
addr = RP(startBufferAddress);
for (i = 0; i < RP(bufferCount)-1; i++) {
*(unsigned short *)(addr + (i*RP(bufferSize))) = i+1;
}
*(unsigned short *)(addr + (i*RP(bufferSize))) = BUF_FREE_WO_NEXT;
RP(alignSize) = alignSize; /* Store alignment size in control header */
RP(freeList) = 0; /* point to the first free block */
return((void *)rp);
} /* end of osCreateRegion */