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
|
/*++
Copyright (c) 1991 Microsoft Corporation
Module Name:
heap.c
Abstract:
Contains a heap allocator function.
Author:
Dan Lafferty (danl) 10-Jul-1991
Environment:
User Mode - Win32
Revision History:
10-Jul-1991 danl
Ported from LM2.0
--*/
// static char *SCCSID = "@(#)heap.c 9.1 86/10/12";
//
// Simple heap allocator for small heaps in shared memory areas.
//
#include <windef.h> // USHORT definitions
#include <heap.h> // Constants, macros, etc.
#include <align.h> // ROUND_UP_COUNT
LPBYTE heap = 0; // Pointer to start of heap
DWORD heapln = 0; // Length of heap
/*
* Msgheapalloc - simple heap allocator
*
* This function allocates blocks out of a far heap.
* It assumes that when it is called the static variable
* heap points to the far heap and the static variable heapln
* contains the length of the far heap.
*
* Msgheapalloc (cb)
*
* ENTRY
* cb - number of bytes to allocate including header
*
* RETURN
* index in far heap to start of block of length cb, or
* INULL if no such block can be found or if cb < sizeof(HEAPHDR).
*
* This function maintains a heap in which all
* blocks are implicitly linked. The header of a block is
* three bytes long. It contains the size of the block including
* the header and a one-byte flag which indicates whether the block
* is allocated or not. Any non-zero value indicates that a block
* is allocated. Note: Msgheapalloc() does NOT set the flag when it
* returns a block. It is up to the caller to mark a block as
* allocated. Unlike most heap allocators, Msgheapalloc() returns a
* pointer (index) to the header rather than just past the header.
* It does this because the message logging routines will need to
* know the lengths of blocks they process. Also, in addition to
* indicating that a block is allocated, the flag byte will be used
* to indicate the type of the block (i.e. single block message,
* multi-block message header, etc.). Since the logging routines
* will use the size of a block, it must be exactly the size
* requested.
*
* The algorithm used was chosen to minimize the size of the
* heap managing routines and to conform to the requirements
* of the logging routines.
*
* SIDE EFFECTS
*
* Changes the structure of the heap.
*/
DWORD
Msgheapalloc(
IN DWORD NumBytes // No. of bytes to allocate
)
{
DWORD i; // Index to return
DWORD newi; // New block index
DWORD nexti; // Next block index
DWORD numBytesNew; // New block size
//
// Must request at least siz bytes
//
if(NumBytes < sizeof(HEAPHDR)) {
return(INULL);
}
//
// *ALIGNMENT*
// If necessary, increase the requested size to cause the allocated
// block to fall on a 4-byte aligned boundary.
//
NumBytes = ROUND_UP_COUNT(NumBytes,4);
//
// This loop is used to traverse the heap by following the
// chain of blocks until either the end of the heap is reached
// or a free block of suitable size is found. Coalescing of
// adjacent free blocks is performed herein also.
//
//
// Loop to allocate block
//
for(i = 0; i < heapln; i += HP_SIZE(*HPTR(i))) {
//
// If free block found (hp_flag=0 indicates free),
//
if(HP_FLAG(*HPTR(i)) == 0) {
//
// A free block was found.
// At this point, check to see if the current block can be
// coalesced with the next block. We start with the offset of
// the current block.
nexti = i;
//
// Add to it the size of the next consecutive
// free blocks until we reach the end of the heap, or an
// allocated block is found.
//
while( (nexti < heapln) && (HP_FLAG(*HPTR(nexti))==0) ) {
nexti += HP_SIZE(*HPTR(nexti));
}
//
// Coalesce blocks all free blocks found thus far
//
HP_SIZE(*HPTR(i)) = nexti - i;
//
// At this point, attempt to allocate from the current
// free block. The current free block must be exactly
// the size we want or large enough to split, since we
// must return a block whose size is EXACTLY the size
// requested.
//
if(HP_SIZE(*HPTR(i)) == NumBytes) {
//
// Size is perfect
//
return(i);
}
if(HP_SIZE(*HPTR(i)) >= NumBytes + sizeof(HEAPHDR)) {
//
// If block is splittable, then get the index and size of
// the block that is left over after taking out what is
// needed from this allocate request.
//
newi = i + NumBytes;
numBytesNew = HP_SIZE(*HPTR(i)) - NumBytes;
//
// Create a header for the left-over block by marking
// it as free, and inserting the size.
//
HP_SIZE(*HPTR(newi)) = numBytesNew;
HP_FLAG(*HPTR(newi)) = 0;
//
// Update the header for the allocated block and
// return its index to the caller.
// NOTE: The caller is responsible for marking this block
// as allocated.
//
HP_SIZE(*HPTR(i)) = NumBytes;
return(i);
}
}
}
return(INULL); // Heap full
}
|
