1262566Sdes/* $OpenBSD: monitor_mm.c,v 1.19 2014/01/04 17:50:55 tedu Exp $ */ 298675Sdes/* 398675Sdes * Copyright 2002 Niels Provos <provos@citi.umich.edu> 498675Sdes * All rights reserved. 598675Sdes * 698675Sdes * Redistribution and use in source and binary forms, with or without 798675Sdes * modification, are permitted provided that the following conditions 898675Sdes * are met: 998675Sdes * 1. Redistributions of source code must retain the above copyright 1098675Sdes * notice, this list of conditions and the following disclaimer. 1198675Sdes * 2. Redistributions in binary form must reproduce the above copyright 1298675Sdes * notice, this list of conditions and the following disclaimer in the 1398675Sdes * documentation and/or other materials provided with the distribution. 1498675Sdes * 1598675Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1698675Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1798675Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1898675Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1998675Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2098675Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2198675Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2298675Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2398675Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2498675Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2598675Sdes */ 2698675Sdes 2798675Sdes#include "includes.h" 2898675Sdes 29162852Sdes#include <sys/types.h> 3098937Sdes#ifdef HAVE_SYS_MMAN_H 3198675Sdes#include <sys/mman.h> 3298937Sdes#endif 33162852Sdes#include <sys/param.h> 34162852Sdes#include "openbsd-compat/sys-tree.h" 3598675Sdes 36162852Sdes#include <errno.h> 37162852Sdes#include <stdarg.h> 38262566Sdes#include <stddef.h> 39255767Sdes#include <stdlib.h> 40162852Sdes#include <string.h> 41162852Sdes 42162852Sdes#include "xmalloc.h" 4398675Sdes#include "ssh.h" 4498675Sdes#include "log.h" 4598675Sdes#include "monitor_mm.h" 4698675Sdes 4798675Sdesstatic int 4898675Sdesmm_compare(struct mm_share *a, struct mm_share *b) 4998675Sdes{ 50262566Sdes ptrdiff_t diff = (char *)a->address - (char *)b->address; 51106121Sdes 52106121Sdes if (diff == 0) 53106121Sdes return (0); 54106121Sdes else if (diff < 0) 55106121Sdes return (-1); 56106121Sdes else 57106121Sdes return (1); 5898675Sdes} 5998675Sdes 6098675SdesRB_GENERATE(mmtree, mm_share, next, mm_compare) 6198675Sdes 6298675Sdesstatic struct mm_share * 6398675Sdesmm_make_entry(struct mm_master *mm, struct mmtree *head, 6498675Sdes void *address, size_t size) 6598675Sdes{ 6698675Sdes struct mm_share *tmp, *tmp2; 6798675Sdes 6898675Sdes if (mm->mmalloc == NULL) 69258343Sdes tmp = xcalloc(1, sizeof(struct mm_share)); 7098675Sdes else 7198675Sdes tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share)); 7298675Sdes tmp->address = address; 7398675Sdes tmp->size = size; 7498675Sdes 7598675Sdes tmp2 = RB_INSERT(mmtree, head, tmp); 7698675Sdes if (tmp2 != NULL) 77262566Sdes fatal("mm_make_entry(%p): double address %p->%p(%zu)", 78262566Sdes mm, tmp2, address, size); 7998675Sdes 8098675Sdes return (tmp); 8198675Sdes} 8298675Sdes 8398675Sdes/* Creates a shared memory area of a certain size */ 8498675Sdes 8598675Sdesstruct mm_master * 8698675Sdesmm_create(struct mm_master *mmalloc, size_t size) 8798675Sdes{ 8898675Sdes void *address; 8998675Sdes struct mm_master *mm; 9098675Sdes 9198675Sdes if (mmalloc == NULL) 92258343Sdes mm = xcalloc(1, sizeof(struct mm_master)); 9398675Sdes else 9498675Sdes mm = mm_xmalloc(mmalloc, sizeof(struct mm_master)); 9598675Sdes 9698675Sdes /* 9798675Sdes * If the memory map has a mm_master it can be completely 9898675Sdes * shared including authentication between the child 9998675Sdes * and the client. 10098675Sdes */ 10198675Sdes mm->mmalloc = mmalloc; 10298675Sdes 103106121Sdes address = xmmap(size); 104146998Sdes if (address == (void *)MAP_FAILED) 105262566Sdes fatal("mmap(%zu): %s", size, strerror(errno)); 10698675Sdes 10798675Sdes mm->address = address; 10898675Sdes mm->size = size; 10998675Sdes 11098675Sdes RB_INIT(&mm->rb_free); 11198675Sdes RB_INIT(&mm->rb_allocated); 11298675Sdes 11398675Sdes mm_make_entry(mm, &mm->rb_free, address, size); 11498675Sdes 11598675Sdes return (mm); 11698675Sdes} 11798675Sdes 11898675Sdes/* Frees either the allocated or the free list */ 11998675Sdes 12098675Sdesstatic void 12198675Sdesmm_freelist(struct mm_master *mmalloc, struct mmtree *head) 12298675Sdes{ 12398675Sdes struct mm_share *mms, *next; 12498675Sdes 12598675Sdes for (mms = RB_ROOT(head); mms; mms = next) { 12698675Sdes next = RB_NEXT(mmtree, head, mms); 12798675Sdes RB_REMOVE(mmtree, head, mms); 12898675Sdes if (mmalloc == NULL) 129255767Sdes free(mms); 13098675Sdes else 13198675Sdes mm_free(mmalloc, mms); 13298675Sdes } 13398675Sdes} 13498675Sdes 13598675Sdes/* Destroys a memory mapped area */ 13698675Sdes 13798675Sdesvoid 13898675Sdesmm_destroy(struct mm_master *mm) 13998675Sdes{ 14098675Sdes mm_freelist(mm->mmalloc, &mm->rb_free); 14198675Sdes mm_freelist(mm->mmalloc, &mm->rb_allocated); 14298675Sdes 143106121Sdes#ifdef HAVE_MMAP 14498675Sdes if (munmap(mm->address, mm->size) == -1) 145262566Sdes fatal("munmap(%p, %zu): %s", mm->address, mm->size, 14698675Sdes strerror(errno)); 14798937Sdes#else 14899060Sdes fatal("%s: UsePrivilegeSeparation=yes and Compression=yes not supported", 14998937Sdes __func__); 15098937Sdes#endif 15198675Sdes if (mm->mmalloc == NULL) 152255767Sdes free(mm); 15398675Sdes else 15498675Sdes mm_free(mm->mmalloc, mm); 15598675Sdes} 15698675Sdes 15798675Sdesvoid * 15898675Sdesmm_xmalloc(struct mm_master *mm, size_t size) 15998675Sdes{ 16098675Sdes void *address; 16198675Sdes 16298675Sdes address = mm_malloc(mm, size); 16398675Sdes if (address == NULL) 164262566Sdes fatal("%s: mm_malloc(%zu)", __func__, size); 165258343Sdes memset(address, 0, size); 16698675Sdes return (address); 16798675Sdes} 16898675Sdes 16998675Sdes 17098675Sdes/* Allocates data from a memory mapped area */ 17198675Sdes 17298675Sdesvoid * 17398675Sdesmm_malloc(struct mm_master *mm, size_t size) 17498675Sdes{ 17598675Sdes struct mm_share *mms, *tmp; 17698675Sdes 17798675Sdes if (size == 0) 17898675Sdes fatal("mm_malloc: try to allocate 0 space"); 179106121Sdes if (size > SIZE_T_MAX - MM_MINSIZE + 1) 180106121Sdes fatal("mm_malloc: size too big"); 18198675Sdes 182106121Sdes size = ((size + (MM_MINSIZE - 1)) / MM_MINSIZE) * MM_MINSIZE; 18398675Sdes 18498675Sdes RB_FOREACH(mms, mmtree, &mm->rb_free) { 18598675Sdes if (mms->size >= size) 18698675Sdes break; 18798675Sdes } 18898675Sdes 18998675Sdes if (mms == NULL) 19098675Sdes return (NULL); 19198675Sdes 19298675Sdes /* Debug */ 19398675Sdes memset(mms->address, 0xd0, size); 19498675Sdes 19598675Sdes tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size); 19698675Sdes 19798675Sdes /* Does not change order in RB tree */ 19898675Sdes mms->size -= size; 199262566Sdes mms->address = (char *)mms->address + size; 20098675Sdes 20198675Sdes if (mms->size == 0) { 20298675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 20398675Sdes if (mm->mmalloc == NULL) 204255767Sdes free(mms); 20598675Sdes else 20698675Sdes mm_free(mm->mmalloc, mms); 20798675Sdes } 20898675Sdes 20998675Sdes return (tmp->address); 21098675Sdes} 21198675Sdes 21298675Sdes/* Frees memory in a memory mapped area */ 21398675Sdes 21498675Sdesvoid 21598675Sdesmm_free(struct mm_master *mm, void *address) 21698675Sdes{ 21798675Sdes struct mm_share *mms, *prev, tmp; 21898675Sdes 21998675Sdes tmp.address = address; 22098675Sdes mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp); 22198675Sdes if (mms == NULL) 22298675Sdes fatal("mm_free(%p): can not find %p", mm, address); 22398675Sdes 22498675Sdes /* Debug */ 22598675Sdes memset(mms->address, 0xd0, mms->size); 22698675Sdes 22798675Sdes /* Remove from allocated list and insert in free list */ 22898675Sdes RB_REMOVE(mmtree, &mm->rb_allocated, mms); 22998675Sdes if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL) 23098675Sdes fatal("mm_free(%p): double address %p", mm, address); 23198675Sdes 23298675Sdes /* Find previous entry */ 23398675Sdes prev = mms; 23498675Sdes if (RB_LEFT(prev, next)) { 23598675Sdes prev = RB_LEFT(prev, next); 23698675Sdes while (RB_RIGHT(prev, next)) 23798675Sdes prev = RB_RIGHT(prev, next); 23898675Sdes } else { 23998675Sdes if (RB_PARENT(prev, next) && 24098675Sdes (prev == RB_RIGHT(RB_PARENT(prev, next), next))) 24198675Sdes prev = RB_PARENT(prev, next); 24298675Sdes else { 24398675Sdes while (RB_PARENT(prev, next) && 24498675Sdes (prev == RB_LEFT(RB_PARENT(prev, next), next))) 24598675Sdes prev = RB_PARENT(prev, next); 24698675Sdes prev = RB_PARENT(prev, next); 24798675Sdes } 24898675Sdes } 24998675Sdes 25098675Sdes /* Check if range does not overlap */ 25198675Sdes if (prev != NULL && MM_ADDRESS_END(prev) > address) 252262566Sdes fatal("mm_free: memory corruption: %p(%zu) > %p", 253262566Sdes prev->address, prev->size, address); 25498675Sdes 25598675Sdes /* See if we can merge backwards */ 25698675Sdes if (prev != NULL && MM_ADDRESS_END(prev) == address) { 25798675Sdes prev->size += mms->size; 25898675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 25998675Sdes if (mm->mmalloc == NULL) 260255767Sdes free(mms); 26198675Sdes else 26298675Sdes mm_free(mm->mmalloc, mms); 26398675Sdes } else 26498675Sdes prev = mms; 26598675Sdes 26698675Sdes if (prev == NULL) 26798675Sdes return; 26898675Sdes 26998675Sdes /* Check if we can merge forwards */ 27098675Sdes mms = RB_NEXT(mmtree, &mm->rb_free, prev); 27198675Sdes if (mms == NULL) 27298675Sdes return; 27398675Sdes 27498675Sdes if (MM_ADDRESS_END(prev) > mms->address) 275262566Sdes fatal("mm_free: memory corruption: %p < %p(%zu)", 276262566Sdes mms->address, prev->address, prev->size); 27798675Sdes if (MM_ADDRESS_END(prev) != mms->address) 27898675Sdes return; 27998675Sdes 28098675Sdes prev->size += mms->size; 28198675Sdes RB_REMOVE(mmtree, &mm->rb_free, mms); 28298675Sdes 28398675Sdes if (mm->mmalloc == NULL) 284255767Sdes free(mms); 28598675Sdes else 28698675Sdes mm_free(mm->mmalloc, mms); 28798675Sdes} 28898675Sdes 28998675Sdesstatic void 29098675Sdesmm_sync_list(struct mmtree *oldtree, struct mmtree *newtree, 29198675Sdes struct mm_master *mm, struct mm_master *mmold) 29298675Sdes{ 29398675Sdes struct mm_master *mmalloc = mm->mmalloc; 29498675Sdes struct mm_share *mms, *new; 29598675Sdes 29698675Sdes /* Sync free list */ 29798675Sdes RB_FOREACH(mms, mmtree, oldtree) { 29898675Sdes /* Check the values */ 29998675Sdes mm_memvalid(mmold, mms, sizeof(struct mm_share)); 30098675Sdes mm_memvalid(mm, mms->address, mms->size); 30198675Sdes 30298675Sdes new = mm_xmalloc(mmalloc, sizeof(struct mm_share)); 30398675Sdes memcpy(new, mms, sizeof(struct mm_share)); 30498675Sdes RB_INSERT(mmtree, newtree, new); 30598675Sdes } 30698675Sdes} 30798675Sdes 30898675Sdesvoid 30998675Sdesmm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc) 31098675Sdes{ 31198675Sdes struct mm_master *mm; 31298675Sdes struct mm_master *mmalloc; 31398675Sdes struct mm_master *mmold; 31498675Sdes struct mmtree rb_free, rb_allocated; 31598675Sdes 31698675Sdes debug3("%s: Share sync", __func__); 31798675Sdes 31898675Sdes mm = *pmm; 31998675Sdes mmold = mm->mmalloc; 32098675Sdes mm_memvalid(mmold, mm, sizeof(*mm)); 32198675Sdes 32298675Sdes mmalloc = mm_create(NULL, mm->size); 32398675Sdes mm = mm_xmalloc(mmalloc, sizeof(struct mm_master)); 32498675Sdes memcpy(mm, *pmm, sizeof(struct mm_master)); 32598675Sdes mm->mmalloc = mmalloc; 32698675Sdes 32798675Sdes rb_free = mm->rb_free; 32898675Sdes rb_allocated = mm->rb_allocated; 32998675Sdes 33098675Sdes RB_INIT(&mm->rb_free); 33198675Sdes RB_INIT(&mm->rb_allocated); 33298675Sdes 33398675Sdes mm_sync_list(&rb_free, &mm->rb_free, mm, mmold); 33498675Sdes mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold); 33598675Sdes 33698675Sdes mm_destroy(mmold); 33798675Sdes 33898675Sdes *pmm = mm; 33998675Sdes *pmmalloc = mmalloc; 34098675Sdes 34198675Sdes debug3("%s: Share sync end", __func__); 34298675Sdes} 34398675Sdes 34498675Sdesvoid 34598675Sdesmm_memvalid(struct mm_master *mm, void *address, size_t size) 34698675Sdes{ 347262566Sdes void *end = (char *)address + size; 34898675Sdes 34998675Sdes if (address < mm->address) 35098675Sdes fatal("mm_memvalid: address too small: %p", address); 35198675Sdes if (end < address) 35298675Sdes fatal("mm_memvalid: end < address: %p < %p", end, address); 353262566Sdes if (end > MM_ADDRESS_END(mm)) 35498675Sdes fatal("mm_memvalid: address too large: %p", address); 35598675Sdes} 356