← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to tools/vmalloc/vmprivate.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/vmalloc/vmprivate.c
 
1
#include        "vmhdr.h"
 
2
 
 
3
static char*    Version = "\n@(#)Vmalloc (AT&T Labs - kpv) 1999-08-05\0\n";
 
4
 
 
5
 
 
6
/*      Private code used in the vmalloc library
 
7
**
 
8
**      Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
 
9
*/
 
10
 
 
11
/* Get more memory for a region */
 
12
#if __STD_C
 
13
static Block_t* vmextend(reg Vmalloc_t* vm, size_t size, Vmsearch_f searchf )
 
14
#else
 
15
static Block_t* vmextend(vm, size, searchf )
 
16
reg Vmalloc_t*  vm;             /* region to increase in size   */
 
17
size_t          size;           /* desired amount of space      */
 
18
Vmsearch_f      searchf;        /* tree search function         */
 
19
#endif
 
20
{
 
21
        reg size_t      s;
 
22
        reg Seg_t*      seg;
 
23
        reg Block_t     *bp, *t;
 
24
        reg Vmuchar_t*  addr;
 
25
        reg Vmdata_t*   vd = vm->data;
 
26
        reg Vmemory_f   memoryf = vm->disc->memoryf;
 
27
        reg Vmexcept_f  exceptf = vm->disc->exceptf;
 
28
 
 
29
        GETPAGESIZE(_Vmpagesize);
 
30
 
 
31
        if(vd->incr <= 0) /* this is just _Vmheap on the first call */
 
32
                vd->incr = 4*_Vmpagesize;
 
33
 
 
34
        /* Get slightly more for administrative data */
 
35
        s = size + sizeof(Seg_t) + sizeof(Block_t) + sizeof(Head_t) + 2*ALIGN;
 
36
        if(s <= size)   /* size was too large and we have wrapped around */
 
37
                return NIL(Block_t*);
 
38
        if((size = ROUND(s,vd->incr)) < s)
 
39
                return NIL(Block_t*);
 
40
 
 
41
        /* see if we can extend the current segment */
 
42
        if(!(seg = vd->seg) )
 
43
                addr = NIL(Vmuchar_t*);
 
44
        else
 
45
        {       if(!vd->wild || SEG(vd->wild) != seg)
 
46
                        s = 0;
 
47
                else
 
48
                {       s = SIZE(vd->wild) + sizeof(Head_t);
 
49
                        if((s = (s/vd->incr)*vd->incr) == size)
 
50
                                size += vd->incr;
 
51
                }
 
52
                addr = (Vmuchar_t*)(*memoryf)(vm,seg->addr,seg->extent,
 
53
                                          seg->extent+size-s,vm->disc);
 
54
                if(!addr)
 
55
                        seg = NIL(Seg_t*);
 
56
                else
 
57
                {       /**/ASSERT(addr == (Vmuchar_t*)seg->addr);
 
58
                        addr += seg->extent;
 
59
                        size -= s;
 
60
                }
 
61
        }
 
62
 
 
63
        while(!addr)    /* try to get space */
 
64
        {       if((addr = (Vmuchar_t*)(*memoryf)(vm,NIL(Void_t*),0,size,vm->disc)) )
 
65
                        break;
 
66
 
 
67
                /* check with exception handler to see if we should continue */
 
68
                if(!exceptf)
 
69
                        return NIL(Block_t*);
 
70
                else
 
71
                {       int     rv, lock;
 
72
                        lock = vd->mode&VM_LOCK;
 
73
                        vd->mode &= ~VM_LOCK;
 
74
                        rv = (*exceptf)(vm,VM_NOMEM,(Void_t*)size,vm->disc);
 
75
                        vd->mode |= lock;
 
76
                        if(rv <= 0)
 
77
                        {       if(rv == 0)
 
78
                                        vd->mode |= VM_AGAIN;
 
79
                                return NIL(Block_t*);
 
80
                        }
 
81
                }
 
82
        }
 
83
 
 
84
        if(seg)
 
85
        {       /* extending current segment */
 
86
                bp = BLOCK(seg->baddr); /**/ ASSERT((SIZE(bp)&~BITS) == 0);
 
87
                                        /**/ ASSERT(SEG(bp) == seg);
 
88
 
 
89
                if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE) )
 
90
                {       if(!ISPFREE(SIZE(bp)) )
 
91
                                SIZE(bp) = size - sizeof(Head_t);
 
92
                        else
 
93
                        {       /**/ ASSERT(searchf);
 
94
                                bp = LAST(bp);
 
95
                                if(bp == vd->wild)
 
96
                                        vd->wild = NIL(Block_t*);
 
97
                                else    REMOVE(vd,bp,INDEX(SIZE(bp)),t,(*searchf));
 
98
                                SIZE(bp) += size;
 
99
                        }
 
100
                }
 
101
                else
 
102
                {       if(seg->free)
 
103
                        {       bp = seg->free;
 
104
                                seg->free = NIL(Block_t*);
 
105
                                SIZE(bp) += size;
 
106
                        }
 
107
                        else    SIZE(bp) = size - sizeof(Head_t);
 
108
                }
 
109
 
 
110
                seg->size += size;
 
111
                seg->extent += size;
 
112
                seg->baddr += size;
 
113
        }
 
114
        else
 
115
        {       /* creating a new segment */
 
116
                reg Seg_t       *sp, *lastsp;
 
117
 
 
118
                if((s = (size_t)(VLONG(addr)%ALIGN)) != 0)
 
119
                        addr += ALIGN-s;
 
120
 
 
121
                seg = (Seg_t*)addr;
 
122
                seg->vm = vm;
 
123
                seg->addr = (Void_t*)(addr - (s ? ALIGN-s : 0));
 
124
                seg->extent = size;
 
125
                seg->baddr = addr + size - (s ? 2*ALIGN : 0);
 
126
                seg->free = NIL(Block_t*);
 
127
                bp = SEGBLOCK(seg);
 
128
                SEG(bp) = seg;
 
129
                SIZE(bp) = seg->baddr - (Vmuchar_t*)bp - 2*sizeof(Head_t);
 
130
 
 
131
                /* NOTE: for Vmbest, Vmdebug and Vmprofile the region's segment list
 
132
                   is reversely ordered by addresses. This is so that we can easily
 
133
                   check for the wild block.
 
134
                */
 
135
                lastsp = NIL(Seg_t*);
 
136
                sp = vd->seg;
 
137
                if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE))
 
138
                        for(; sp; lastsp = sp, sp = sp->next)
 
139
                                if(seg->addr > sp->addr)
 
140
                                        break;
 
141
                seg->next = sp;
 
142
                if(lastsp)
 
143
                        lastsp->next = seg;
 
144
                else    vd->seg = seg;
 
145
 
 
146
                seg->size = SIZE(bp);
 
147
        }
 
148
 
 
149
        /* make a fake header for possible segmented memory */
 
150
        t = NEXT(bp);
 
151
        SEG(t) = seg;
 
152
        SIZE(t) = BUSY;
 
153
 
 
154
        /* see if the wild block is still wild */
 
155
        if((t = vd->wild) && (seg = SEG(t)) != vd->seg)
 
156
        {       CLRPFREE(SIZE(NEXT(t)));
 
157
                if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE) )
 
158
                {       SIZE(t) |= BUSY|JUNK;
 
159
                        LINK(t) = CACHE(vd)[C_INDEX(SIZE(t))];
 
160
                        CACHE(vd)[C_INDEX(SIZE(t))] = t;
 
161
                }
 
162
                else    seg->free = t;
 
163
 
 
164
                vd->wild = NIL(Block_t*);
 
165
        }
 
166
 
 
167
        return bp;
 
168
}
 
169
 
 
170
/* Truncate a segment if possible */
 
171
#if __STD_C
 
172
static int vmtruncate(Vmalloc_t* vm, Seg_t* seg, size_t size, int exact)
 
173
#else
 
174
static int vmtruncate(vm, seg, size, exact)
 
175
Vmalloc_t*      vm;     /* containing region            */
 
176
Seg_t*          seg;    /* the one to be truncated      */
 
177
size_t          size;   /* amount of free space         */
 
178
int             exact;  /* amount given was exact       */
 
179
#endif
 
180
{
 
181
        reg Void_t*     caddr;
 
182
        reg Seg_t*      last;
 
183
        reg Vmdata_t*   vd = vm->data;
 
184
        reg Vmemory_f   memoryf = vm->disc->memoryf;
 
185
 
 
186
        caddr = seg->addr;
 
187
 
 
188
        if(size < seg->size)
 
189
        {       reg size_t      less;
 
190
 
 
191
                /* the truncated amount must satisfy the discipline requirement */
 
192
                if((less = vm->disc->round) <= 0)
 
193
                        less = _Vmpagesize;
 
194
                less = (size/less)*less;
 
195
                less = (less/ALIGN)*ALIGN;
 
196
 
 
197
                if(!exact)      /* only truncate multiples of incr */
 
198
                        less = (less/vd->incr)*vd->incr;
 
199
 
 
200
                if(less > 0 && size > less && (size-less) < sizeof(Block_t) )
 
201
                        less -= vd->incr;
 
202
 
 
203
                if(less <= 0 ||
 
204
                   (*memoryf)(vm,caddr,seg->extent,seg->extent-less,vm->disc) != caddr)
 
205
                        return -1;
 
206
 
 
207
                seg->extent -= less;
 
208
                seg->size -= less;
 
209
                seg->baddr -= less;
 
210
                SIZE(BLOCK(seg->baddr)) = BUSY;
 
211
                return 0;
 
212
        }
 
213
 
 
214
        /* unlink segment from region */
 
215
        if(seg == vd->seg)
 
216
        {       vd->seg = seg->next;
 
217
                last = NIL(Seg_t*);
 
218
        }
 
219
        else
 
220
        {       for(last = vd->seg; last->next != seg; last = last->next)
 
221
                        ;
 
222
                last->next = seg->next;
 
223
        }
 
224
 
 
225
        /* now delete it */
 
226
        if((*memoryf)(vm,caddr,seg->extent,0,vm->disc) == caddr)
 
227
                return 0;
 
228
 
 
229
        /* space reduction failed, reinsert segment */
 
230
        if(last)
 
231
        {       seg->next = last->next;
 
232
                last->next = seg;
 
233
        }
 
234
        else
 
235
        {       seg->next = vd->seg;
 
236
                vd->seg = seg;
 
237
        }
 
238
        return -1;
 
239
}
 
240
 
 
241
/* Externally visible names but local to library */
 
242
Vmextern_t      _Vmextern =
 
243
{       vmextend,                                               /* _Vmextend    */
 
244
        vmtruncate,                                             /* _Vmtruncate  */
 
245
        0,                                                      /* _Vmpagesize  */
 
246
        NIL(char*(*)_ARG_((char*,char*,int))),                  /* _Vmstrcpy    */
 
247
        NIL(char*(*)_ARG_((Vmulong_t,int))),                    /* _Vmitoa      */
 
248
        NIL(void(*)_ARG_((Vmalloc_t*,
 
249
                          Vmuchar_t*,Vmuchar_t*,size_t,size_t))), /* _Vmtrace   */
 
250
        NIL(void(*)_ARG_((Vmalloc_t*)))                         /* _Vmpfclose   */
 
251
};