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