1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 /* 30 * XXX This stuff should be in usr/src/common, to be shared by boot 31 * code, kernel DR, and busra stuff. 32 * 33 * NOTE: We are only using the next-> link. The prev-> link is 34 * not used in the implementation. 35 */ 36 #include <sys/types.h> 37 #include <sys/memlist.h> 38 #include <sys/kmem.h> 39 #include <sys/cmn_err.h> 40 #include <sys/pci_impl.h> 41 #include <sys/debug.h> 42 43 extern int pci_boot_debug; 44 #define dprintf if (pci_boot_debug) printf 45 46 void 47 memlist_dump(struct memlist *listp) 48 { 49 dprintf("memlist 0x%p content", (void *)listp); 50 while (listp) { 51 dprintf("(0x%x%x, 0x%x%x)", 52 (int)(listp->address >> 32), (int)listp->address, 53 (int)(listp->size >> 32), (int)listp->size); 54 listp = listp->next; 55 } 56 } 57 58 struct memlist * 59 memlist_alloc() 60 { 61 return ((struct memlist *)kmem_zalloc(sizeof (struct memlist), 62 KM_SLEEP)); 63 } 64 65 void 66 memlist_free(struct memlist *buf) 67 { 68 kmem_free(buf, sizeof (struct memlist)); 69 } 70 71 /* insert in the order of addresses */ 72 void 73 memlist_insert(struct memlist **listp, uint64_t addr, uint64_t size) 74 { 75 int merge_left, merge_right; 76 struct memlist *entry; 77 struct memlist *prev = 0, *next; 78 79 /* find the location in list */ 80 next = *listp; 81 while (next && next->address < addr) { 82 prev = next; 83 next = prev->next; 84 } 85 86 merge_left = (prev && addr == prev->address + prev->size); 87 merge_right = (next && addr + size == next->address); 88 if (merge_left && merge_right) { 89 prev->size += size + next->size; 90 prev->next = next->next; 91 memlist_free(next); 92 return; 93 } 94 95 if (merge_left) { 96 prev->size += size; 97 return; 98 } 99 100 if (merge_right) { 101 next->address = addr; 102 next->size += size; 103 return; 104 } 105 106 entry = memlist_alloc(); 107 entry->address = addr; 108 entry->size = size; 109 if (prev == 0) { 110 entry->next = *listp; 111 *listp = entry; 112 } else { 113 entry->next = next; 114 prev->next = entry; 115 } 116 } 117 118 /* 119 * Delete memory chunks, assuming list sorted by address 120 */ 121 int 122 memlist_remove(struct memlist **listp, uint64_t addr, uint64_t size) 123 { 124 struct memlist *entry; 125 struct memlist *prev = 0, *next; 126 127 /* a remove can't be done on an empty list */ 128 ASSERT(*listp); 129 130 /* find the location in list */ 131 next = *listp; 132 while (next && (next->address + next->size < addr)) { 133 prev = next; 134 next = prev->next; 135 } 136 137 if (next == 0 || (addr < next->address)) { 138 dprintf("memlist_remove: addr 0x%x%x, size 0x%x%x" 139 " not contained in list\n", 140 (int)(addr >> 32), (int)addr, 141 (int)(size >> 32), (int)size); 142 memlist_dump(*listp); 143 return (-1); 144 } 145 146 if (addr > next->address) { 147 uint64_t oldsize = next->size; 148 next->size = addr - next->address; 149 if ((next->address + oldsize) > (addr + size)) { 150 entry = memlist_alloc(); 151 entry->address = addr + size; 152 entry->size = next->address + oldsize - addr - size; 153 entry->next = next->next; 154 next->next = entry; 155 } 156 } else if ((next->address + next->size) > (addr + size)) { 157 /* addr == next->address */ 158 next->address = addr + size; 159 next->size -= size; 160 } else { 161 /* the entire chunk is deleted */ 162 if (prev == 0) { 163 *listp = next->next; 164 } else { 165 prev->next = next->next; 166 } 167 memlist_free(next); 168 } 169 return (0); 170 } 171 172 /* 173 * find and claim a memory chunk of given size, first fit 174 */ 175 uint64_t 176 memlist_find(struct memlist **listp, uint64_t size, int align) 177 { 178 uint_t delta = 0; 179 uint64_t paddr; 180 struct memlist *prev = 0, *next; 181 182 /* find the chunk with sufficient size */ 183 next = *listp; 184 while (next && (next->size < size + align - 1)) { 185 prev = next; 186 next = prev->next; 187 } 188 189 if (next == 0) 190 return (0); 191 192 paddr = next->address; 193 if (align) 194 delta = (uint_t)(paddr & (align - 1)); 195 if (delta) 196 paddr += align - delta; 197 (void) memlist_remove(listp, paddr, size); 198 return (paddr); 199 } 200 201 /* 202 * Make a copy of memlist 203 */ 204 struct memlist * 205 memlist_dup(struct memlist *listp) 206 { 207 struct memlist *head = 0, *prev = 0; 208 209 while (listp) { 210 struct memlist *entry = memlist_alloc(); 211 entry->address = listp->address; 212 entry->size = listp->size; 213 entry->next = 0; 214 if (prev) 215 prev->next = entry; 216 else 217 head = entry; 218 prev = entry; 219 listp = listp->next; 220 } 221 222 return (head); 223 } 224 225 int 226 memlist_count(struct memlist *listp) 227 { 228 int count = 0; 229 while (listp) { 230 count++; 231 listp = listp->next; 232 } 233 234 return (count); 235 } 236