← Back to branch summary

~ubuntu-branches/ubuntu/dapper/openssh/dapper

« back to all changes in this revision

Viewing changes to monitor_mm.c

  • Committer: Bazaar Package Importer
  • Author(s): Noah Meyerhans
  • Date: 2006-10-31 17:53:38 UTC
  • Revision ID: james.westby@ubuntu.com-20061031175338-kh299ada2qc2kzlb
Tags: upstream-3.8.1p1
Import upstream version 3.8.1p1

Show diffs side-by-side

added added

removed removed

Lines of Context:
monitor_mm.c
 
1
/*
 
2
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 * 1. Redistributions of source code must retain the above copyright
 
9
 *    notice, this list of conditions and the following disclaimer.
 
10
 * 2. Redistributions in binary form must reproduce the above copyright
 
11
 *    notice, this list of conditions and the following disclaimer in the
 
12
 *    documentation and/or other materials provided with the distribution.
 
13
 *
 
14
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 
15
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
16
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
17
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 
18
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
19
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
20
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
21
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
22
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
23
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
24
 */
 
25
 
 
26
#include "includes.h"
 
27
RCSID("$OpenBSD: monitor_mm.c,v 1.8 2002/08/02 14:43:15 millert Exp $");
 
28
 
 
29
#ifdef HAVE_SYS_MMAN_H
 
30
#include <sys/mman.h>
 
31
#endif
 
32
 
 
33
#include "ssh.h"
 
34
#include "xmalloc.h"
 
35
#include "log.h"
 
36
#include "monitor_mm.h"
 
37
 
 
38
static int
 
39
mm_compare(struct mm_share *a, struct mm_share *b)
 
40
{
 
41
        long diff = (char *)a->address - (char *)b->address;
 
42
 
 
43
        if (diff == 0)
 
44
                return (0);
 
45
        else if (diff < 0)
 
46
                return (-1);
 
47
        else
 
48
                return (1);
 
49
}
 
50
 
 
51
RB_GENERATE(mmtree, mm_share, next, mm_compare)
 
52
 
 
53
static struct mm_share *
 
54
mm_make_entry(struct mm_master *mm, struct mmtree *head,
 
55
    void *address, size_t size)
 
56
{
 
57
        struct mm_share *tmp, *tmp2;
 
58
 
 
59
        if (mm->mmalloc == NULL)
 
60
                tmp = xmalloc(sizeof(struct mm_share));
 
61
        else
 
62
                tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share));
 
63
        tmp->address = address;
 
64
        tmp->size = size;
 
65
 
 
66
        tmp2 = RB_INSERT(mmtree, head, tmp);
 
67
        if (tmp2 != NULL)
 
68
                fatal("mm_make_entry(%p): double address %p->%p(%lu)",
 
69
                    mm, tmp2, address, (u_long)size);
 
70
 
 
71
        return (tmp);
 
72
}
 
73
 
 
74
/* Creates a shared memory area of a certain size */
 
75
 
 
76
struct mm_master *
 
77
mm_create(struct mm_master *mmalloc, size_t size)
 
78
{
 
79
        void *address;
 
80
        struct mm_master *mm;
 
81
 
 
82
        if (mmalloc == NULL)
 
83
                mm = xmalloc(sizeof(struct mm_master));
 
84
        else
 
85
                mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
 
86
 
 
87
        /*
 
88
         * If the memory map has a mm_master it can be completely
 
89
         * shared including authentication between the child
 
90
         * and the client.
 
91
         */
 
92
        mm->mmalloc = mmalloc;
 
93
 
 
94
        address = xmmap(size);
 
95
        if (address == MAP_FAILED)
 
96
                fatal("mmap(%lu): %s", (u_long)size, strerror(errno));
 
97
 
 
98
        mm->address = address;
 
99
        mm->size = size;
 
100
 
 
101
        RB_INIT(&mm->rb_free);
 
102
        RB_INIT(&mm->rb_allocated);
 
103
 
 
104
        mm_make_entry(mm, &mm->rb_free, address, size);
 
105
 
 
106
        return (mm);
 
107
}
 
108
 
 
109
/* Frees either the allocated or the free list */
 
110
 
 
111
static void
 
112
mm_freelist(struct mm_master *mmalloc, struct mmtree *head)
 
113
{
 
114
        struct mm_share *mms, *next;
 
115
 
 
116
        for (mms = RB_ROOT(head); mms; mms = next) {
 
117
                next = RB_NEXT(mmtree, head, mms);
 
118
                RB_REMOVE(mmtree, head, mms);
 
119
                if (mmalloc == NULL)
 
120
                        xfree(mms);
 
121
                else
 
122
                        mm_free(mmalloc, mms);
 
123
        }
 
124
}
 
125
 
 
126
/* Destroys a memory mapped area */
 
127
 
 
128
void
 
129
mm_destroy(struct mm_master *mm)
 
130
{
 
131
        mm_freelist(mm->mmalloc, &mm->rb_free);
 
132
        mm_freelist(mm->mmalloc, &mm->rb_allocated);
 
133
 
 
134
#ifdef HAVE_MMAP
 
135
        if (munmap(mm->address, mm->size) == -1)
 
136
                fatal("munmap(%p, %lu): %s", mm->address, (u_long)mm->size,
 
137
                    strerror(errno));
 
138
#else
 
139
        fatal("%s: UsePrivilegeSeparation=yes and Compression=yes not supported",
 
140
            __func__);
 
141
#endif
 
142
        if (mm->mmalloc == NULL)
 
143
                xfree(mm);
 
144
        else
 
145
                mm_free(mm->mmalloc, mm);
 
146
}
 
147
 
 
148
void *
 
149
mm_xmalloc(struct mm_master *mm, size_t size)
 
150
{
 
151
        void *address;
 
152
 
 
153
        address = mm_malloc(mm, size);
 
154
        if (address == NULL)
 
155
                fatal("%s: mm_malloc(%lu)", __func__, (u_long)size);
 
156
        return (address);
 
157
}
 
158
 
 
159
 
 
160
/* Allocates data from a memory mapped area */
 
161
 
 
162
void *
 
163
mm_malloc(struct mm_master *mm, size_t size)
 
164
{
 
165
        struct mm_share *mms, *tmp;
 
166
 
 
167
        if (size == 0)
 
168
                fatal("mm_malloc: try to allocate 0 space");
 
169
        if (size > SIZE_T_MAX - MM_MINSIZE + 1)
 
170
                fatal("mm_malloc: size too big");
 
171
 
 
172
        size = ((size + (MM_MINSIZE - 1)) / MM_MINSIZE) * MM_MINSIZE;
 
173
 
 
174
        RB_FOREACH(mms, mmtree, &mm->rb_free) {
 
175
                if (mms->size >= size)
 
176
                        break;
 
177
        }
 
178
 
 
179
        if (mms == NULL)
 
180
                return (NULL);
 
181
 
 
182
        /* Debug */
 
183
        memset(mms->address, 0xd0, size);
 
184
 
 
185
        tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size);
 
186
 
 
187
        /* Does not change order in RB tree */
 
188
        mms->size -= size;
 
189
        mms->address = (u_char *)mms->address + size;
 
190
 
 
191
        if (mms->size == 0) {
 
192
                RB_REMOVE(mmtree, &mm->rb_free, mms);
 
193
                if (mm->mmalloc == NULL)
 
194
                        xfree(mms);
 
195
                else
 
196
                        mm_free(mm->mmalloc, mms);
 
197
        }
 
198
 
 
199
        return (tmp->address);
 
200
}
 
201
 
 
202
/* Frees memory in a memory mapped area */
 
203
 
 
204
void
 
205
mm_free(struct mm_master *mm, void *address)
 
206
{
 
207
        struct mm_share *mms, *prev, tmp;
 
208
 
 
209
        tmp.address = address;
 
210
        mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp);
 
211
        if (mms == NULL)
 
212
                fatal("mm_free(%p): can not find %p", mm, address);
 
213
 
 
214
        /* Debug */
 
215
        memset(mms->address, 0xd0, mms->size);
 
216
 
 
217
        /* Remove from allocated list and insert in free list */
 
218
        RB_REMOVE(mmtree, &mm->rb_allocated, mms);
 
219
        if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL)
 
220
                fatal("mm_free(%p): double address %p", mm, address);
 
221
 
 
222
        /* Find previous entry */
 
223
        prev = mms;
 
224
        if (RB_LEFT(prev, next)) {
 
225
                prev = RB_LEFT(prev, next);
 
226
                while (RB_RIGHT(prev, next))
 
227
                        prev = RB_RIGHT(prev, next);
 
228
        } else {
 
229
                if (RB_PARENT(prev, next) &&
 
230
                    (prev == RB_RIGHT(RB_PARENT(prev, next), next)))
 
231
                        prev = RB_PARENT(prev, next);
 
232
                else {
 
233
                        while (RB_PARENT(prev, next) &&
 
234
                            (prev == RB_LEFT(RB_PARENT(prev, next), next)))
 
235
                                prev = RB_PARENT(prev, next);
 
236
                        prev = RB_PARENT(prev, next);
 
237
                }
 
238
        }
 
239
 
 
240
        /* Check if range does not overlap */
 
241
        if (prev != NULL && MM_ADDRESS_END(prev) > address)
 
242
                fatal("mm_free: memory corruption: %p(%lu) > %p",
 
243
                    prev->address, (u_long)prev->size, address);
 
244
 
 
245
        /* See if we can merge backwards */
 
246
        if (prev != NULL && MM_ADDRESS_END(prev) == address) {
 
247
                prev->size += mms->size;
 
248
                RB_REMOVE(mmtree, &mm->rb_free, mms);
 
249
                if (mm->mmalloc == NULL)
 
250
                        xfree(mms);
 
251
                else
 
252
                        mm_free(mm->mmalloc, mms);
 
253
        } else
 
254
                prev = mms;
 
255
 
 
256
        if (prev == NULL)
 
257
                return;
 
258
 
 
259
        /* Check if we can merge forwards */
 
260
        mms = RB_NEXT(mmtree, &mm->rb_free, prev);
 
261
        if (mms == NULL)
 
262
                return;
 
263
 
 
264
        if (MM_ADDRESS_END(prev) > mms->address)
 
265
                fatal("mm_free: memory corruption: %p < %p(%lu)",
 
266
                    mms->address, prev->address, (u_long)prev->size);
 
267
        if (MM_ADDRESS_END(prev) != mms->address)
 
268
                return;
 
269
 
 
270
        prev->size += mms->size;
 
271
        RB_REMOVE(mmtree, &mm->rb_free, mms);
 
272
 
 
273
        if (mm->mmalloc == NULL)
 
274
                xfree(mms);
 
275
        else
 
276
                mm_free(mm->mmalloc, mms);
 
277
}
 
278
 
 
279
static void
 
280
mm_sync_list(struct mmtree *oldtree, struct mmtree *newtree,
 
281
    struct mm_master *mm, struct mm_master *mmold)
 
282
{
 
283
        struct mm_master *mmalloc = mm->mmalloc;
 
284
        struct mm_share *mms, *new;
 
285
 
 
286
        /* Sync free list */
 
287
        RB_FOREACH(mms, mmtree, oldtree) {
 
288
                /* Check the values */
 
289
                mm_memvalid(mmold, mms, sizeof(struct mm_share));
 
290
                mm_memvalid(mm, mms->address, mms->size);
 
291
 
 
292
                new = mm_xmalloc(mmalloc, sizeof(struct mm_share));
 
293
                memcpy(new, mms, sizeof(struct mm_share));
 
294
                RB_INSERT(mmtree, newtree, new);
 
295
        }
 
296
}
 
297
 
 
298
void
 
299
mm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc)
 
300
{
 
301
        struct mm_master *mm;
 
302
        struct mm_master *mmalloc;
 
303
        struct mm_master *mmold;
 
304
        struct mmtree rb_free, rb_allocated;
 
305
 
 
306
        debug3("%s: Share sync", __func__);
 
307
 
 
308
        mm = *pmm;
 
309
        mmold = mm->mmalloc;
 
310
        mm_memvalid(mmold, mm, sizeof(*mm));
 
311
 
 
312
        mmalloc = mm_create(NULL, mm->size);
 
313
        mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
 
314
        memcpy(mm, *pmm, sizeof(struct mm_master));
 
315
        mm->mmalloc = mmalloc;
 
316
 
 
317
        rb_free = mm->rb_free;
 
318
        rb_allocated = mm->rb_allocated;
 
319
 
 
320
        RB_INIT(&mm->rb_free);
 
321
        RB_INIT(&mm->rb_allocated);
 
322
 
 
323
        mm_sync_list(&rb_free, &mm->rb_free, mm, mmold);
 
324
        mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold);
 
325
 
 
326
        mm_destroy(mmold);
 
327
 
 
328
        *pmm = mm;
 
329
        *pmmalloc = mmalloc;
 
330
 
 
331
        debug3("%s: Share sync end", __func__);
 
332
}
 
333
 
 
334
void
 
335
mm_memvalid(struct mm_master *mm, void *address, size_t size)
 
336
{
 
337
        void *end = (u_char *)address + size;
 
338
 
 
339
        if (address < mm->address)
 
340
                fatal("mm_memvalid: address too small: %p", address);
 
341
        if (end < address)
 
342
                fatal("mm_memvalid: end < address: %p < %p", end, address);
 
343
        if (end > (void *)((u_char *)mm->address + mm->size))
 
344
                fatal("mm_memvalid: address too large: %p", address);
 
345
}