blob: 1483ee62d014cdf8d058689eeed0dee72b731bd8 (
plain)
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
|
/*
* Copyright (c) 1995 The University of Utah and
* the Computer Systems Laboratory at the University of Utah (CSL).
* All rights reserved.
*
* Permission to use, copy, modify and distribute this software is hereby
* granted provided that (1) source code retains these copyright, permission,
* and disclaimer notices, and (2) redistributions including binaries
* reproduce the notices in supporting documentation, and (3) all advertising
* materials mentioning features or use of this software display the following
* acknowledgement: ``This product includes software developed by the
* Computer Systems Laboratory at the University of Utah.''
*
* THE UNIVERSITY OF UTAH AND CSL ALLOW FREE USE OF THIS SOFTWARE IN ITS "AS
* IS" CONDITION. THE UNIVERSITY OF UTAH AND CSL DISCLAIM ANY LIABILITY OF
* ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* CSL requests users of this software to return to csl-dist@cs.utah.edu any
* improvements that they make and grant CSL redistribution rights.
*/
#undef NDEBUG // LMM assert()s are O(1) and vital
#include <assert.h>
#include <lmm/lmm.h>
#include <lmm/lmm_types.h>
void lmm_free(lmm_t *lmm, void *block, vm_size_t size)
{
struct lmm_region *reg;
struct lmm_node *node = (struct lmm_node*)
((vm_offset_t)block & ~ALIGN_MASK);
struct lmm_node *prevnode, *nextnode;
assert(lmm != 0);
assert(block != 0);
assert(size > 0);
size = (((vm_offset_t)block & ALIGN_MASK) + size + ALIGN_MASK)
& ~ALIGN_MASK;
/* First find the region to add this block to. */
for (reg = lmm->regions; ; reg = reg->next)
{
assert(reg != 0);
assert((reg->nodes == 0 && reg->free == 0)
|| ((vm_offset_t)reg->nodes >= reg->min));
if (((vm_offset_t)node >= reg->min)
&& ((vm_offset_t)node < reg->max))
break;
}
/* Record the newly freed space in the region's free space counter. */
reg->free += size;
assert(reg->free <= reg->max - reg->min);
/* Now find the location in that region's free list
at which to add the node. */
for (prevnode = 0, nextnode = reg->nodes;
(nextnode != 0) && (nextnode < node);
prevnode = nextnode, nextnode = nextnode->next);
/* Coalesce the new free chunk into the previous chunk if possible. */
if ((prevnode) &&
((vm_offset_t)prevnode + prevnode->size >= (vm_offset_t)node))
{
assert((vm_offset_t)prevnode + prevnode->size
== (vm_offset_t)node);
/* Coalesce prevnode with nextnode if possible. */
if (((vm_offset_t)nextnode)
&& ((vm_offset_t)node + size >= (vm_offset_t)nextnode))
{
assert((vm_offset_t)node + size
== (vm_offset_t)nextnode);
prevnode->size += size + nextnode->size;
prevnode->next = nextnode->next;
}
else
{
/* Not possible -
just grow prevnode around newly freed memory. */
prevnode->size += size;
}
}
else
{
/* Insert the new node into the free list. */
if (prevnode)
prevnode->next = node;
else
reg->nodes = node;
/* Try coalescing the new node with the nextnode. */
if ((nextnode) &&
(vm_offset_t)node + size >= (vm_offset_t)nextnode)
{
node->size = size + nextnode->size;
node->next = nextnode->next;
}
else
{
node->size = size;
node->next = nextnode;
}
}
}
|
