← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/runtime/mcentral.c

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/runtime/mcentral.c
 
1
// 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 "malloc.h"
 
19
 
 
20
static bool MCentral_Grow(MCentral *c);
 
21
static void* MCentral_Alloc(MCentral *c);
 
22
static void MCentral_Free(MCentral *c, void *v);
 
23
 
 
24
// Initialize a single central free list.
 
25
void
 
26
runtime·MCentral_Init(MCentral *c, int32 sizeclass)
 
27
{
 
28
        c->sizeclass = sizeclass;
 
29
        runtime·MSpanList_Init(&c->nonempty);
 
30
        runtime·MSpanList_Init(&c->empty);
 
31
}
 
32
 
 
33
// Allocate up to n objects from the central free list.
 
34
// Return the number of objects allocated.
 
35
// The objects are linked together by their first words.
 
36
// On return, *pstart points at the first object and *pend at the last.
 
37
int32
 
38
runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
 
39
{
 
40
        MLink *first, *last, *v;
 
41
        int32 i;
 
42
 
 
43
        runtime·lock(c);
 
44
        // Replenish central list if empty.
 
45
        if(runtime·MSpanList_IsEmpty(&c->nonempty)) {
 
46
                if(!MCentral_Grow(c)) {
 
47
                        runtime·unlock(c);
 
48
                        *pfirst = nil;
 
49
                        return 0;
 
50
                }
 
51
        }
 
52
 
 
53
        // Copy from list, up to n.
 
54
        // First one is guaranteed to work, because we just grew the list.
 
55
        first = MCentral_Alloc(c);
 
56
        last = first;
 
57
        for(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) {
 
58
                last->next = v;
 
59
                last = v;
 
60
        }
 
61
        last->next = nil;
 
62
        c->nfree -= i;
 
63
 
 
64
        runtime·unlock(c);
 
65
        *pfirst = first;
 
66
        return i;
 
67
}
 
68
 
 
69
// Helper: allocate one object from the central free list.
 
70
static void*
 
71
MCentral_Alloc(MCentral *c)
 
72
{
 
73
        MSpan *s;
 
74
        MLink *v;
 
75
 
 
76
        if(runtime·MSpanList_IsEmpty(&c->nonempty))
 
77
                return nil;
 
78
        s = c->nonempty.next;
 
79
        s->ref++;
 
80
        v = s->freelist;
 
81
        s->freelist = v->next;
 
82
        if(s->freelist == nil) {
 
83
                runtime·MSpanList_Remove(s);
 
84
                runtime·MSpanList_Insert(&c->empty, s);
 
85
        }
 
86
        return v;
 
87
}
 
88
 
 
89
// Free n objects back into the central free list.
 
90
// Return the number of objects allocated.
 
91
// The objects are linked together by their first words.
 
92
// On return, *pstart points at the first object and *pend at the last.
 
93
void
 
94
runtime·MCentral_FreeList(MCentral *c, int32 n, MLink *start)
 
95
{
 
96
        MLink *v, *next;
 
97
 
 
98
        // Assume next == nil marks end of list.
 
99
        // n and end would be useful if we implemented
 
100
        // the transfer cache optimization in the TODO above.
 
101
        USED(n);
 
102
 
 
103
        runtime·lock(c);
 
104
        for(v=start; v; v=next) {
 
105
                next = v->next;
 
106
                MCentral_Free(c, v);
 
107
        }
 
108
        runtime·unlock(c);
 
109
}
 
110
 
 
111
// Helper: free one object back into the central free list.
 
112
static void
 
113
MCentral_Free(MCentral *c, void *v)
 
114
{
 
115
        MSpan *s;
 
116
        MLink *p;
 
117
        int32 size;
 
118
 
 
119
        // Find span for v.
 
120
        s = runtime·MHeap_Lookup(&runtime·mheap, v);
 
121
        if(s == nil || s->ref == 0)
 
122
                runtime·throw("invalid free");
 
123
 
 
124
        // Move to nonempty if necessary.
 
125
        if(s->freelist == nil) {
 
126
                runtime·MSpanList_Remove(s);
 
127
                runtime·MSpanList_Insert(&c->nonempty, s);
 
128
        }
 
129
 
 
130
        // Add v back to s's free list.
 
131
        p = v;
 
132
        p->next = s->freelist;
 
133
        s->freelist = p;
 
134
        c->nfree++;
 
135
 
 
136
        // If s is completely freed, return it to the heap.
 
137
        if(--s->ref == 0) {
 
138
                size = runtime·class_to_size[c->sizeclass];
 
139
                runtime·MSpanList_Remove(s);
 
140
                runtime·unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
 
141
                *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
 
142
                s->freelist = nil;
 
143
                c->nfree -= (s->npages << PageShift) / size;
 
144
                runtime·unlock(c);
 
145
                runtime·MHeap_Free(&runtime·mheap, s, 0);
 
146
                runtime·lock(c);
 
147
        }
 
148
}
 
149
 
 
150
void
 
151
runtime·MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
 
152
{
 
153
        int32 size;
 
154
        int32 npages;
 
155
 
 
156
        npages = runtime·class_to_allocnpages[sizeclass];
 
157
        size = runtime·class_to_size[sizeclass];
 
158
        *npagesp = npages;
 
159
        *sizep = size;
 
160
        *nobj = (npages << PageShift) / size;
 
161
}
 
162
 
 
163
// Fetch a new span from the heap and
 
164
// carve into objects for the free list.
 
165
static bool
 
166
MCentral_Grow(MCentral *c)
 
167
{
 
168
        int32 i, n, npages;
 
169
        uintptr size;
 
170
        MLink **tailp, *v;
 
171
        byte *p;
 
172
        MSpan *s;
 
173
 
 
174
        runtime·unlock(c);
 
175
        runtime·MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
 
176
        s = runtime·MHeap_Alloc(&runtime·mheap, npages, c->sizeclass, 0);
 
177
        if(s == nil) {
 
178
                // TODO(rsc): Log out of memory
 
179
                runtime·lock(c);
 
180
                return false;
 
181
        }
 
182
 
 
183
        // Carve span into sequence of blocks.
 
184
        tailp = &s->freelist;
 
185
        p = (byte*)(s->start << PageShift);
 
186
        s->limit = p + size*n;
 
187
        for(i=0; i<n; i++) {
 
188
                v = (MLink*)p;
 
189
                *tailp = v;
 
190
                tailp = &v->next;
 
191
                p += size;
 
192
        }
 
193
        *tailp = nil;
 
194
        runtime·markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
 
195
 
 
196
        runtime·lock(c);
 
197
        c->nfree += n;
 
198
        runtime·MSpanList_Insert(&c->nonempty, s);
 
199
        return true;
 
200
}