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 (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 1996 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27
28 #include <stdio.h>
29 #include <string.h>
30 #include <stdlib.h>
31 #include <libintl.h>
32 #include "pkglib.h"
33
34 /*
35 * This is the module responsible for allocating and maintaining lists that
36 * require allocation of memory. For certain lists, large chunks are
37 * allocated once to contain a large number of entries in each chunk (bl_*
38 * for block list). The other approach involves the augmentation of linked
39 * lists, each entry of which is alloc'd individually.
40 */
41 #define ERR_CS_ALLOC "ERROR: Cannot allocate control structure for %s array."
42 #define ERR_MEM_ALLOC "ERROR: Cannot allocate memory for %s array."
43
44 #define MAX_ARRAYS 50
45
46 #define ARRAY_END(x) (bl_cs_array[x]->cur_segment->avail_ptr)
47 #define REC_SIZE(x) (bl_cs_array[x]->struct_size)
48 #define EOSEG(x) (bl_cs_array[x]->cur_segment->eoseg_ptr)
49 #define GET_AVAIL(x) (ARRAY_END(x) + REC_SIZE(x))
50
51 struct alloc_seg {
52 char *seg_ptr; /* ptr to the allocated block */
53 char *avail_ptr; /* ptr to the next available list element */
54 char *eoseg_ptr; /* last byte in the segment */
55 int full; /* segment has no available space */
56 struct alloc_seg *next; /* next record */
57 };
58
59 struct blk_list_cs {
60 int struct_size; /* size of a single list element */
61 int count_per_block; /* number of list elements per block */
62 int block_size; /* just to save time - alloc size */
63 int data_handle; /* list_handle for pointer array */
64 struct alloc_seg *alloc_segs; /* memory pool */
65
66 struct alloc_seg *cur_segment; /* the current allocated segment */
67 int total_elem; /* total elements stored */
68 int contiguous; /* use realloc to grow */
69 char *desc; /* description of the list */
70 };
71
72 static struct blk_list_cs *bl_cs_array[MAX_ARRAYS];
73 static int next_array_elem;
74
75 /* Support functions */
76 static int
invalid_handle(int list_handle)77 invalid_handle(int list_handle)
78 {
79 if (list_handle < 0 || list_handle >= next_array_elem)
80 return (1);
81
82 return (0);
83 }
84
85 static int
invalid_record(int list_handle,int recno)86 invalid_record(int list_handle, int recno)
87 {
88 if (invalid_handle(list_handle))
89 return (1);
90
91 if (recno < 0 || recno > bl_cs_array[list_handle]->total_elem)
92 return (1);
93
94 return (0);
95 }
96
97 static void
free_list(int list_handle)98 free_list(int list_handle)
99 {
100 struct blk_list_cs *bl_ptr;
101 struct alloc_seg *segstr_ptr, *nextstr_ptr;
102
103 /* Make sure this wasn't free'd earlier */
104 if (bl_cs_array[list_handle] == NULL)
105 return;
106
107 bl_ptr = bl_cs_array[list_handle];
108
109 /* First free the alloc_seg list. */
110 segstr_ptr = bl_ptr->alloc_segs;
111
112 if (segstr_ptr) {
113 do {
114 nextstr_ptr = segstr_ptr->next;
115
116 /* Free the memory block. */
117 free((void *)segstr_ptr->seg_ptr);
118
119 /* Free the control structure. */
120 free((void *)segstr_ptr);
121 segstr_ptr = nextstr_ptr;
122 } while (segstr_ptr);
123 }
124
125 /* Free the block control structure. */
126 free((void *)bl_ptr->desc);
127 free((void *)bl_ptr);
128
129 bl_cs_array[list_handle] = NULL;
130 }
131
132 /* Allocate another alloc_seg structure. */
133 static int
alloc_next_seg(struct blk_list_cs * bl_ptr)134 alloc_next_seg(struct blk_list_cs *bl_ptr)
135 {
136 struct alloc_seg *new_alloc_cs;
137
138 if (bl_ptr->contiguous) {
139 int offset_to_avail, seg_size, new_size;
140 struct alloc_seg *alloc_segment;
141
142 if (bl_ptr->alloc_segs) {
143 alloc_segment = bl_ptr->alloc_segs;
144
145 offset_to_avail = (alloc_segment->avail_ptr -
146 alloc_segment->seg_ptr);
147 seg_size = (alloc_segment->eoseg_ptr -
148 alloc_segment->seg_ptr);
149 new_size = (seg_size + bl_ptr->block_size);
150 } else {
151 if ((bl_ptr->alloc_segs =
152 (struct alloc_seg *)calloc(1,
153 sizeof (struct alloc_seg))) == NULL) {
154 logerr(gettext(ERR_CS_ALLOC), (bl_ptr->desc ?
155 bl_ptr->desc : "an unknown"));
156 return (0);
157 }
158
159 alloc_segment = bl_ptr->alloc_segs;
160
161 offset_to_avail = 0;
162 seg_size = 0;
163 new_size = bl_ptr->block_size;
164 }
165
166 bl_ptr->cur_segment = alloc_segment;
167
168 if ((alloc_segment->seg_ptr =
169 (char *)realloc((void *)alloc_segment->seg_ptr,
170 (unsigned)new_size)) == NULL) {
171 logerr(gettext(ERR_MEM_ALLOC), (bl_ptr->desc ?
172 bl_ptr->desc : "an unknown"));
173 return (0);
174 }
175
176 alloc_segment->next = NULL;
177
178 /* reset the status */
179 alloc_segment->full = 0;
180
181 /* readjust the original pointers */
182 alloc_segment->avail_ptr = alloc_segment->seg_ptr +
183 offset_to_avail;
184 alloc_segment->eoseg_ptr = alloc_segment->seg_ptr + new_size;
185
186 (void) memset(alloc_segment->avail_ptr, '\000',
187 bl_ptr->block_size);
188 } else {
189 /* Allocate the control structure and link it into the list. */
190 if ((new_alloc_cs = (struct alloc_seg *)malloc(
191 sizeof (struct alloc_seg))) == NULL) {
192 logerr(gettext(ERR_CS_ALLOC), (bl_ptr->desc ?
193 bl_ptr->desc : "an unknown"));
194 return (0);
195 }
196
197 if (bl_ptr->alloc_segs == NULL) {
198 /*
199 * If this is the first allocation, then initialize
200 * the head pointer and set cur_segment to this first
201 * block of memory.
202 */
203 bl_ptr->alloc_segs = new_alloc_cs;
204 } else {
205 /*
206 * Otherwise, point the current cur_segment to the
207 * next one and then point to the new one.
208 */
209 bl_ptr->cur_segment->next = new_alloc_cs;
210 }
211
212 new_alloc_cs->next = NULL;
213 bl_ptr->cur_segment = new_alloc_cs;
214
215 new_alloc_cs->full = 0;
216
217 /* Now allocate the block of memory that this controls. */
218 if ((new_alloc_cs->seg_ptr = calloc(bl_ptr->count_per_block,
219 bl_ptr->struct_size)) == NULL) {
220 logerr(gettext(ERR_MEM_ALLOC), (bl_ptr->desc ?
221 bl_ptr->desc : "an unknown"));
222 return (0);
223 }
224
225 new_alloc_cs->avail_ptr = new_alloc_cs->seg_ptr;
226 new_alloc_cs->eoseg_ptr = (new_alloc_cs->seg_ptr +
227 bl_ptr->block_size);
228 }
229
230 return (1);
231 }
232
233 /*
234 * These first functions (beginning with bl_*) manage simple block lists. The
235 * pointers returned, may get lost if they aren't assigned to an array or
236 * something. While individual records can be obtained by record number, the
237 * process isn't very efficient. Look to the array management section
238 * (ar_*)for an easily administrable list.
239 */
240
241 /*
242 * Create a block list. Allocate memory for a block list structure and
243 * initialize that structure. This doesn't actually allocate memory for the
244 * list yet, just the controlling data structure. Returns -1 on failure and a
245 * valid block list handle otherwise.
246 *
247 * NOTE: At the time of writing, it was not seen as important to recover block
248 * pointers made available with a bl_free() (two of these at most in
249 * pkginstall). If this became important later, we could trade efficiency for
250 * speed by ignoring next_array_elem and actually scanning through the array
251 * for a NULL pointer and then return that.
252 */
253 int
bl_create(int count_per_block,int struct_size,char * desc)254 bl_create(int count_per_block, int struct_size, char *desc)
255 {
256 struct blk_list_cs *bl_ptr;
257 int retval;
258
259 if ((bl_cs_array[next_array_elem] =
260 (struct blk_list_cs *)calloc(1, sizeof (struct blk_list_cs))) ==
261 NULL) {
262 logerr(gettext(ERR_CS_ALLOC), (desc ? desc : "an unknown"));
263 return (-1);
264 }
265
266 bl_ptr = bl_cs_array[next_array_elem];
267 retval = next_array_elem++;
268
269 bl_ptr->data_handle = -1;
270 bl_ptr->struct_size = struct_size;
271 bl_ptr->count_per_block = count_per_block;
272 bl_ptr->block_size = (count_per_block * struct_size);
273 bl_ptr->desc = strdup((desc ? desc : "unknown"));
274
275 return (retval);
276 }
277
278 /*
279 * Get the next available entry in the list. This will allocate memory as
280 * required based on the initialization values in bl_create(). Returns a
281 * pointer to the allocated memory segment or NULL if operation was not
282 * possible.
283 */
284 char *
bl_next_avail(int list_handle)285 bl_next_avail(int list_handle)
286 {
287 struct blk_list_cs *bl_ptr;
288 char *retval;
289
290 if (invalid_handle(list_handle))
291 return (NULL);
292
293 bl_ptr = bl_cs_array[list_handle];
294
295 /*
296 * Allocate more memory if none is allocated yet or our last access
297 * filled the allotted segment.
298 */
299 if (bl_ptr->cur_segment == NULL || bl_ptr->cur_segment->full)
300 if (!alloc_next_seg(bl_ptr))
301 return (NULL);
302
303 /* Get the correct pointer. */
304 retval = bl_ptr->cur_segment->avail_ptr;
305
306 /* Advance it and mark if full. */
307 bl_ptr->cur_segment->avail_ptr += bl_ptr->struct_size;
308 bl_ptr->total_elem++;
309
310 if (bl_ptr->cur_segment->avail_ptr >= bl_ptr->cur_segment->eoseg_ptr)
311 bl_ptr->cur_segment->full = 1;
312
313 return (retval);
314 }
315
316 char *
bl_get_record(int list_handle,int recno)317 bl_get_record(int list_handle, int recno)
318 {
319 struct blk_list_cs *bl_ptr;
320 struct alloc_seg *cur_as_ptr;
321 int cur_rec = 0;
322
323 if (invalid_record(list_handle, recno))
324 return (NULL);
325
326 bl_ptr = bl_cs_array[list_handle];
327
328 cur_as_ptr = bl_ptr->alloc_segs;
329
330 while (recno > (cur_rec + bl_ptr->count_per_block)) {
331 cur_as_ptr = cur_as_ptr->next;
332
333 if (cur_as_ptr == NULL)
334 return (NULL);
335
336 cur_rec += bl_ptr->count_per_block;
337 }
338
339 /*
340 * Now cur_as_ptr points to the allocated segment bearing the
341 * intended record and all we do now is move down that by the
342 * remaining record lengths.
343 */
344
345 return ((char *)cur_as_ptr + ((recno - cur_rec) * bl_ptr->struct_size));
346 }
347
348 void
bl_free(int list_handle)349 bl_free(int list_handle)
350 {
351 int cur_handle;
352
353 if (list_handle == -1) {
354 for (cur_handle = 0; cur_handle < next_array_elem;
355 cur_handle++) {
356 free_list(cur_handle);
357 }
358 } else {
359 if (invalid_handle(list_handle))
360 return;
361
362 free_list(list_handle);
363 }
364 }
365
366 /*
367 * These are the array management functions. They insert into (and can return
368 * a pointer to) a contiguous list of pointers to stuff. This keeps
369 * everything together in a very handy package and is very similar in
370 * appearance to the arrays created by the old AT&T code. The method for
371 * presenting the interface is entirely different, however.
372 */
373
374 /*
375 * This constructs, maintains and returns pointers into a growable array of
376 * pointers to structures of the form
377 * struct something *array[n]
378 * The last element in the array is always NULL.
379 */
380 int
ar_create(int count_per_block,int struct_size,char * desc)381 ar_create(int count_per_block, int struct_size, char *desc)
382 {
383 int data_handle, retval;
384 char ar_desc[60];
385 struct blk_list_cs *array_ptr;
386
387 if ((data_handle = bl_create(count_per_block, struct_size, desc)) == -1)
388 return (-1);
389
390 sprintf(ar_desc, "%s pointer", desc);
391 if ((retval = bl_create(count_per_block, sizeof (char *),
392 ar_desc)) == -1)
393 return (-1);
394
395 array_ptr = bl_cs_array[retval];
396
397 array_ptr->contiguous = 1;
398 array_ptr->data_handle = data_handle;
399
400 return (retval);
401 }
402
403 /* Return a pointer to the first element in the array. */
404 char **
ar_get_head(int list_handle)405 ar_get_head(int list_handle)
406 {
407 if (invalid_handle(list_handle) ||
408 bl_cs_array[list_handle]->alloc_segs == NULL)
409 return (NULL);
410
411 return ((char **)bl_cs_array[list_handle]->alloc_segs->seg_ptr);
412 }
413
414 /*
415 * Free up the entry in the array indicated by index, but hold onto it for
416 * future use.
417 */
418 int
ar_delete(int list_handle,int index)419 ar_delete(int list_handle, int index)
420 {
421 char **array;
422 char *deleted_rec;
423 int i;
424 struct blk_list_cs *list_ptr, *data_ptr;
425
426 if ((array = ar_get_head(list_handle)) == NULL)
427 return (0);
428
429 if (invalid_record(list_handle, index))
430 return (0);
431
432 /* Get the pointer to the array control structure. */
433 list_ptr = bl_cs_array[list_handle];
434
435 if (!(list_ptr->contiguous))
436 return (0); /* This isn't an array. */
437
438 data_ptr = bl_cs_array[list_ptr->data_handle];
439
440 /*
441 * Since this looks just like an array. Record the pointer being
442 * deleted for insertion into the avail list at the end and move all
443 * elements below it up one.
444 */
445 deleted_rec = array[index];
446
447 for (i = index; array[i] != NULL; i++)
448 array[i] = array[i+1];
449
450 /*
451 * Now insert the deleted entry into the avails list after the NULL
452 * and adjust the avail_ptr to point to the NULL again.
453 */
454 array[i] = deleted_rec;
455 list_ptr->alloc_segs->avail_ptr -= list_ptr->struct_size;
456
457 /* Adjust other entries in the control structure. */
458 list_ptr->alloc_segs->full = 0;
459 list_ptr->total_elem -= 1;
460
461 /* Clear the deleted data area. */
462 (void) memset(deleted_rec, '\000', data_ptr->struct_size);
463
464 return (1);
465 }
466
467 /*
468 * Return a new pointer to a structure pointer. Find an available element in
469 * the array and point it at an available element in the data pool
470 * constructed of block lists. Allocate new memory as necessary.
471 */
472 char **
ar_next_avail(int list_handle)473 ar_next_avail(int list_handle)
474 {
475 struct blk_list_cs *array_ptr;
476 char *data_area, **pointer_area;
477
478 if (invalid_handle(list_handle) ||
479 !(bl_cs_array[list_handle]->contiguous) ||
480 invalid_handle(bl_cs_array[list_handle]->data_handle))
481 return (NULL);
482
483 array_ptr = bl_cs_array[list_handle];
484
485 /*
486 * First see if an avail has already been allocated (it will be right
487 * after the NULL termination of the array if it exists). Return
488 * that, if found.
489 */
490 if ((bl_cs_array[list_handle]->cur_segment != NULL) &&
491 (ARRAY_END(list_handle) + REC_SIZE(list_handle) <
492 EOSEG(list_handle)) &&
493 (*(pointer_area = (char **) GET_AVAIL(list_handle)) != NULL)) {
494 /* We can reclaim a previous deletion. */
495 data_area = *pointer_area;
496
497 *(char **)(ARRAY_END(list_handle)) = data_area; /* reactivate */
498 *pointer_area-- = NULL; /* new end */
499
500 array_ptr->cur_segment->avail_ptr += array_ptr->struct_size;
501 array_ptr->total_elem++;
502 } else {
503 /*
504 * Get the data area first. This is the record we're pointing
505 * to from the array.
506 */
507 data_area = bl_next_avail(array_ptr->data_handle);
508
509 /* Now get the next pointer from the pointer array. */
510 pointer_area = (char **) bl_next_avail(list_handle);
511
512 *pointer_area = data_area;
513
514 /*
515 * The array must be NULL terminated. So, if the block list
516 * structure is full, we have to grow it without resetting
517 * the avail pointer. NOTE: This will only work for a
518 * contiguous list!
519 */
520 if (bl_cs_array[list_handle]->alloc_segs->full) {
521 char **old_list_pointer, **new_list_pointer;
522
523 /*
524 * First grab the old numbers in case realloc() moves
525 * everything.
526 */
527 old_list_pointer = ar_get_head(list_handle);
528
529 /*
530 * Now allocate additional contiguous memory, moving
531 * the original block if necessary.
532 */
533 if (!alloc_next_seg(array_ptr))
534 return (NULL);
535
536 /*
537 * Now determine if everything moved and readjust the
538 * pointer_area if required.
539 */
540 new_list_pointer = ar_get_head(list_handle);
541
542 if (old_list_pointer != new_list_pointer) {
543 pointer_area += (new_list_pointer -
544 old_list_pointer);
545 }
546 }
547 }
548
549 return (pointer_area);
550 }
551
552 /*
553 * Relinquish the array back to the memory pool. Note that there is no method
554 * provided to free *all* arrays.
555 */
556 void
ar_free(int list_handle)557 ar_free(int list_handle)
558 {
559 if (invalid_handle(list_handle))
560 return;
561
562 bl_free(bl_cs_array[list_handle]->data_handle);
563 bl_free(list_handle);
564 }
565