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