OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [runtime/] [mcentral.c] - Blame information for rev 833

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 747 jeremybenn
// Copyright 2009 The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4
 
5
// Central free lists.
6
//
7
// See malloc.h for an overview.
8
//
9
// The MCentral doesn't actually contain the list of free objects; the MSpan does.
10
// Each MCentral is two lists of MSpans: those with free objects (c->nonempty)
11
// and those that are completely allocated (c->empty).
12
//
13
// TODO(rsc): tcmalloc uses a "transfer cache" to split the list
14
// into sections of class_to_transfercount[sizeclass] objects
15
// so that it is faster to move those lists between MCaches and MCentrals.
16
 
17
#include "runtime.h"
18
#include "arch.h"
19
#include "malloc.h"
20
 
21
static bool MCentral_Grow(MCentral *c);
22
static void* MCentral_Alloc(MCentral *c);
23
static void MCentral_Free(MCentral *c, void *v);
24
 
25
// Initialize a single central free list.
26
void
27
runtime_MCentral_Init(MCentral *c, int32 sizeclass)
28
{
29
        c->sizeclass = sizeclass;
30
        runtime_MSpanList_Init(&c->nonempty);
31
        runtime_MSpanList_Init(&c->empty);
32
}
33
 
34
// Allocate up to n objects from the central free list.
35
// Return the number of objects allocated.
36
// The objects are linked together by their first words.
37
// On return, *pstart points at the first object and *pend at the last.
38
int32
39
runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
40
{
41
        MLink *first, *last, *v;
42
        int32 i;
43
 
44
        runtime_lock(c);
45
        // Replenish central list if empty.
46
        if(runtime_MSpanList_IsEmpty(&c->nonempty)) {
47
                if(!MCentral_Grow(c)) {
48
                        runtime_unlock(c);
49
                        *pfirst = nil;
50
                        return 0;
51
                }
52
        }
53
 
54
        // Copy from list, up to n.
55
        // First one is guaranteed to work, because we just grew the list.
56
        first = MCentral_Alloc(c);
57
        last = first;
58
        for(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) {
59
                last->next = v;
60
                last = v;
61
        }
62
        last->next = nil;
63
        c->nfree -= i;
64
 
65
        runtime_unlock(c);
66
        *pfirst = first;
67
        return i;
68
}
69
 
70
// Helper: allocate one object from the central free list.
71
static void*
72
MCentral_Alloc(MCentral *c)
73
{
74
        MSpan *s;
75
        MLink *v;
76
 
77
        if(runtime_MSpanList_IsEmpty(&c->nonempty))
78
                return nil;
79
        s = c->nonempty.next;
80
        s->ref++;
81
        v = s->freelist;
82
        s->freelist = v->next;
83
        if(s->freelist == nil) {
84
                runtime_MSpanList_Remove(s);
85
                runtime_MSpanList_Insert(&c->empty, s);
86
        }
87
        return v;
88
}
89
 
90
// Free n objects back into the central free list.
91
// Return the number of objects allocated.
92
// The objects are linked together by their first words.
93
// On return, *pstart points at the first object and *pend at the last.
94
void
95
runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *start)
96
{
97
        MLink *v, *next;
98
 
99
        // Assume next == nil marks end of list.
100
        // n and end would be useful if we implemented
101
        // the transfer cache optimization in the TODO above.
102
        USED(n);
103
 
104
        runtime_lock(c);
105
        for(v=start; v; v=next) {
106
                next = v->next;
107
                MCentral_Free(c, v);
108
        }
109
        runtime_unlock(c);
110
}
111
 
112
// Helper: free one object back into the central free list.
113
static void
114
MCentral_Free(MCentral *c, void *v)
115
{
116
        MSpan *s;
117
        MLink *p;
118
        int32 size;
119
 
120
        // Find span for v.
121
        s = runtime_MHeap_Lookup(&runtime_mheap, v);
122
        if(s == nil || s->ref == 0)
123
                runtime_throw("invalid free");
124
 
125
        // Move to nonempty if necessary.
126
        if(s->freelist == nil) {
127
                runtime_MSpanList_Remove(s);
128
                runtime_MSpanList_Insert(&c->nonempty, s);
129
        }
130
 
131
        // Add v back to s's free list.
132
        p = v;
133
        p->next = s->freelist;
134
        s->freelist = p;
135
        c->nfree++;
136
 
137
        // If s is completely freed, return it to the heap.
138
        if(--s->ref == 0) {
139
                size = runtime_class_to_size[c->sizeclass];
140
                runtime_MSpanList_Remove(s);
141
                runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
142
                *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
143
                s->freelist = nil;
144
                c->nfree -= (s->npages << PageShift) / size;
145
                runtime_unlock(c);
146
                runtime_MHeap_Free(&runtime_mheap, s, 0);
147
                runtime_lock(c);
148
        }
149
}
150
 
151
void
152
runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
153
{
154
        int32 size;
155
        int32 npages;
156
 
157
        npages = runtime_class_to_allocnpages[sizeclass];
158
        size = runtime_class_to_size[sizeclass];
159
        *npagesp = npages;
160
        *sizep = size;
161
        *nobj = (npages << PageShift) / size;
162
}
163
 
164
// Fetch a new span from the heap and
165
// carve into objects for the free list.
166
static bool
167
MCentral_Grow(MCentral *c)
168
{
169
        int32 i, n, npages;
170
        uintptr size;
171
        MLink **tailp, *v;
172
        byte *p;
173
        MSpan *s;
174
 
175
        runtime_unlock(c);
176
        runtime_MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
177
        s = runtime_MHeap_Alloc(&runtime_mheap, npages, c->sizeclass, 0);
178
        if(s == nil) {
179
                // TODO(rsc): Log out of memory
180
                runtime_lock(c);
181
                return false;
182
        }
183
 
184
        // Carve span into sequence of blocks.
185
        tailp = &s->freelist;
186
        p = (byte*)(s->start << PageShift);
187
        s->limit = p + size*n;
188
        for(i=0; i<n; i++) {
189
                v = (MLink*)p;
190
                *tailp = v;
191
                tailp = &v->next;
192
                p += size;
193
        }
194
        *tailp = nil;
195
        runtime_markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
196
 
197
        runtime_lock(c);
198
        c->nfree += n;
199
        runtime_MSpanList_Insert(&c->nonempty, s);
200
        return true;
201
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.