1/* 2 * Copyright (c) 2010 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 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 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 23 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * Portions of this software have been released under the following terms: 31 * 32 * (c) Copyright 1989-1993 OPEN SOFTWARE FOUNDATION, INC. 33 * (c) Copyright 1989-1993 HEWLETT-PACKARD COMPANY 34 * (c) Copyright 1989-1993 DIGITAL EQUIPMENT CORPORATION 35 * 36 * To anyone who acknowledges that this file is provided "AS IS" 37 * without any express or implied warranty: 38 * permission to use, copy, modify, and distribute this file for any 39 * purpose is hereby granted without fee, provided that the above 40 * copyright notices and this notice appears in all source code copies, 41 * and that none of the names of Open Software Foundation, Inc., Hewlett- 42 * Packard Company or Digital Equipment Corporation be used 43 * in advertising or publicity pertaining to distribution of the software 44 * without specific, written prior permission. Neither Open Software 45 * Foundation, Inc., Hewlett-Packard Company nor Digital 46 * Equipment Corporation makes any representations about the suitability 47 * of this software for any purpose. 48 * 49 * Copyright (c) 2007, Novell, Inc. All rights reserved. 50 * Redistribution and use in source and binary forms, with or without 51 * modification, are permitted provided that the following conditions 52 * are met: 53 * 54 * 1. Redistributions of source code must retain the above copyright 55 * notice, this list of conditions and the following disclaimer. 56 * 2. Redistributions in binary form must reproduce the above copyright 57 * notice, this list of conditions and the following disclaimer in the 58 * documentation and/or other materials provided with the distribution. 59 * 3. Neither the name of Novell Inc. nor the names of its contributors 60 * may be used to endorse or promote products derived from this 61 * this software without specific prior written permission. 62 * 63 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY 64 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 65 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 66 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY 67 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 68 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 69 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 70 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 71 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 72 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 73 * 74 * @APPLE_LICENSE_HEADER_END@ 75 */ 76 77/* 78** 79** NAME: 80** 81** rpclist.h 82** 83** FACILITY: 84** 85** Remote Procedure Call (RPC) 86** 87** ABSTRACT: 88** 89** Various types and macros for list and queue processing. 90** 91** 92*/ 93 94#ifndef _RPCLIST_H 95#define _RPCLIST_H 96 97/***********************************************************************/ 98/* 99 * List Processing. 100 * 101 * The RPC services maintain a number of structures in the form of lists 102 * and queues. Lists are doubly linked with the list head containing both 103 * a pointer to the first element of the list as well as a pointer to the 104 * last element in the list. The elements on these lists are maintained in 105 * first-in first-out order. By maintaining the last element pointer, 106 * elements can be easily added to the end of the list. 107 * 108 * Structures which are going to be used in lists should have a member of 109 * the type rpc_list_t as their first member. 110 * 111 * List descriptors are used to maintain context for lists which are going 112 * to take advantage of memory management optimizations (lookaside lists). 113 * Memory for these lists is obtained in large "chunks", which is then 114 * provided to individual list elements on an as-needed basis. 115 * 116 * ***CAVEAT***: 117 * 118 * The structures kept on lists which are processed by the 119 * RPC_LIST* macros can be kept on only one list at a time. 120 * This is because the macros *assume* the first field of the 121 * structure given to them is a "link" field (an rpc_list_t) 122 * structure. It casts the structure to to a be a pointer to an 123 * rpc_list_t structure and manipulates the fields of it ("next" and 124 * "last"). Enqueuing a structure on a second list would effectively 125 * remove it from the first list since the "next" and "last" fields 126 * would be overwritten. 127 */ 128 129/*int pthd4_get_expiration_np(struct timespec *delta, struct timespec *abstime);*/ 130 131/***********************************************************************/ 132/* 133 * R P C _ L I S T _ T 134 * 135 * This is a list head (or a set of reference pointers in a list element). 136 */ 137 138typedef struct 139{ 140 dce_pointer_t next; /* next element of list */ 141 dce_pointer_t last; /* last element of list in a descriptor or */ 142 /* pointer to the prior element in an element */ 143} rpc_list_t, *rpc_list_p_t; 144 145/***********************************************************************/ 146/* 147 * R P C _ L I S T _ E L E M E N T _ A L L O C _ F N _ T 148 * 149 */ 150 151typedef void (*rpc_list_element_alloc_fn_t) ( 152 dce_pointer_t /*list_element*/ 153 ); 154 155/***********************************************************************/ 156/* 157 * R P C _ L I S T _ E L E M E N T _ F R E E _ F N _ T 158 * 159 */ 160 161typedef void (*rpc_list_element_free_fn_t) ( 162 dce_pointer_t /*list_element*/ 163 ); 164 165/***********************************************************************/ 166/* 167 * R P C _ L I S T _ D E S C _ T 168 * 169 */ 170 171typedef struct 172{ 173 rpc_list_t list_head; 174 unsigned32 max_size; 175 unsigned32 cur_size; 176 unsigned32 element_size; 177 unsigned32 element_type; 178 rpc_list_element_alloc_fn_t alloc_rtn; 179 rpc_list_element_free_fn_t free_rtn; 180 rpc_mutex_t *mutex; 181 rpc_cond_t *cond; 182 boolean32 use_global_mutex; 183} rpc_list_desc_t, *rpc_list_desc_p_t; 184 185/***********************************************************************/ 186/* 187 * R P C _ L O O K A S I D E _ R C B _ T 188 */ 189 190typedef struct 191{ 192 unsigned16 res_id; 193 unsigned16 waiter_cnt; 194 unsigned16 max_wait_times; 195 unsigned16 wait_time; 196 rpc_mutex_t res_lock; 197 rpc_cond_t wait_flg; 198} rpc_lookaside_rcb_t, *rpc_lookaside_rcb_p_t; 199 200#define RPC_C_LOOKASIDE_RES 1 201#define RPC_C_LOOKASIDE_RES_WAIT 1 202#define RPC_C_LOOKASIDE_RES_MAX_WAIT 5 203 204EXTERNAL rpc_lookaside_rcb_t rpc_g_lookaside_rcb; 205 206/***********************************************************************/ 207/* 208 * R P C _ L I S T _ M U T E X _ I N I T 209 * 210 * Initialize the global lookaside list mutex. 211 * 212 * Sample usage: 213 * 214 * RPC_LIST_MUTEX_INIT (0); 215 */ 216#define RPC_LIST_MUTEX_INIT(junk) \ 217{ \ 218 RPC_MUTEX_INIT (rpc_g_lookaside_rcb.res_lock); \ 219 RPC_COND_INIT (rpc_g_lookaside_rcb.wait_flg, \ 220 rpc_g_lookaside_rcb.res_lock); \ 221} 222 223/***********************************************************************/ 224/* 225 * R P C _ L I S T _ I N I T 226 * 227 * Initialize a list head. 228 * 229 * Sample usage: 230 * 231 * rpc_list_t list; 232 * 233 * RPC_LIST_INIT (list); 234 */ 235 236#define RPC_LIST_INIT(list) \ 237{ \ 238 list.next = NULL; \ 239 list.last = NULL; \ 240} 241 242/***********************************************************************/ 243/* 244 * R P C _ L I S T _ E M P T Y 245 * 246 * Determine whether or not a list has any elements left. 247 * 248 * RETURNS: true - list has more elements 249 * false - list has no more elements 250 * 251 * Sample usage: 252 * 253 * rpc_list_t list; 254 * 255 * if (RPC_LIST_EMPTY (list)) ... 256 */ 257 258#define RPC_LIST_EMPTY(list) (list.next == NULL) 259 260/***********************************************************************/ 261/* 262 * R P C _ L I S T _ A D D 263 * 264 * Insert an element after a specified entry in a list. 265 * 266 * Sample usage: 267 * 268 * rpc_list_t list; (listhead) 269 * any_p_t list_element; (location to insert) 270 * any_p_t insert_element; (element to be inserted) 271 * 272 * RPC_LIST_ADD (list, list_element, insert_element, any_p_t); 273 */ 274 275#define RPC_LIST_ADD(list, list_element, insert_element, list_element_type) \ 276{ \ 277 ((rpc_list_p_t) (insert_element))->next = \ 278 ((rpc_list_p_t) (list_element))->next; \ 279 ((rpc_list_p_t) (insert_element))->last = (dce_pointer_t) (list_element); \ 280 if (((rpc_list_p_t) (list_element))->next == NULL) \ 281 { \ 282 (list).last = (dce_pointer_t) (insert_element); \ 283 } \ 284 else \ 285 { \ 286 ((rpc_list_p_t) (((rpc_list_p_t) (list_element))->next))->last = \ 287 (dce_pointer_t) (insert_element); \ 288 } \ 289 ((rpc_list_p_t) (list_element))->next = (dce_pointer_t) (insert_element); \ 290} 291 292/***********************************************************************/ 293/* 294 * R P C _ L I S T _ A D D _ H E A D 295 * 296 * Add an entry to the beginning of a list. 297 * 298 * Sample usage: 299 * 300 * rpc_list_t list; 301 * any_p_t list_element; 302 * 303 * RPC_LIST_ADD_HEAD (list, list_element, any_p_t); 304 */ 305 306#define RPC_LIST_ADD_HEAD(list, list_element, list_element_type) \ 307{ \ 308 if (RPC_LIST_EMPTY (list)) \ 309 { \ 310 (list).next = (list).last = (dce_pointer_t) (list_element); \ 311 ((rpc_list_p_t) (list_element))->next = NULL; \ 312 ((rpc_list_p_t) (list_element))->last = (dce_pointer_t) &(list); \ 313 } \ 314 else \ 315 { \ 316 ((rpc_list_p_t) (list_element))->next = (dce_pointer_t) ((list).next); \ 317 ((rpc_list_p_t) (list_element))->last = (dce_pointer_t) &(list); \ 318 ((rpc_list_p_t)((list).next))->last = (dce_pointer_t) (list_element); \ 319 (list).next = (dce_pointer_t) (list_element); \ 320 } \ 321} 322 323/***********************************************************************/ 324/* 325 * R P C _ L I S T _ A D D _ T A I L 326 * 327 * Add an entry to the end of a list. 328 * 329 * Sample usage: 330 * 331 * rpc_list_t list; 332 * any_p_t list_element; 333 * 334 * RPC_LIST_ADD_TAIL (list, list_element, any_p_t); 335 */ 336 337#define RPC_LIST_ADD_TAIL(list, list_element, list_element_type) \ 338{ \ 339 if (RPC_LIST_EMPTY (list)) \ 340 { \ 341 list.next = (dce_pointer_t) (list_element); \ 342 ((rpc_list_p_t) (list_element))->last = (dce_pointer_t) &(list); \ 343 } \ 344 else \ 345 { \ 346 ((rpc_list_p_t) (list.last))->next = (dce_pointer_t) (list_element); \ 347 ((rpc_list_p_t) (list_element))->last = list.last; \ 348 } \ 349 list.last = (dce_pointer_t) (list_element); \ 350 ((rpc_list_p_t) (list_element))->next = NULL; \ 351} 352 353/***********************************************************************/ 354/* 355 * R P C _ L I S T _ R E M O V E 356 * 357 * Remove an element (pointed to by list_element) from a list. 358 * 359 * Sample usage: 360 * 361 * rpc_list_t list; 362 * any_p_t list_element; 363 * 364 * RPC_LIST_REMOVE (list, list_element); 365 */ 366 367#define RPC_LIST_REMOVE(list, list_element) \ 368{ \ 369 if (list.last == list.next) \ 370 { \ 371 RPC_LIST_INIT (list); \ 372 } \ 373 else \ 374 { \ 375 if (((rpc_list_p_t) (list_element))->next == NULL) \ 376 { \ 377 list.last = ((rpc_list_p_t) (list_element))->last; \ 378 } \ 379 else \ 380 { \ 381 ((rpc_list_p_t) ((rpc_list_p_t) (list_element))->next)->last = \ 382 ((rpc_list_p_t) (list_element))->last; \ 383 } \ 384 ((rpc_list_p_t) ((rpc_list_p_t) (list_element))->last)->next = \ 385 ((rpc_list_p_t) (list_element))->next; \ 386 } \ 387} 388 389/***********************************************************************/ 390/* 391 * R P C _ L I S T _ R E M O V E _ H E A D 392 * 393 * Remove the first entry from a list and return it. If the list is 394 * empty a NULL pointer is returned. Note: This is functionally 395 * equivalent to doing RPC_LIST_EXTRACT (,,1), but is slightly more 396 * efficient. 397 * 398 * Sample usage: 399 * 400 * rpc_list_t list; 401 * any_p_t list_element; 402 * 403 * RPC_LIST_REMOVE_HEAD (list, list_element, any_p_t); 404 */ 405 406#define RPC_LIST_REMOVE_HEAD(list, list_element, list_element_type) \ 407{ \ 408 if (RPC_LIST_EMPTY (list)) \ 409 { \ 410 list_element = NULL; \ 411 } \ 412 else \ 413 { \ 414 RPC_LIST_FIRST (list, list_element, list_element_type); \ 415 RPC_LIST_REMOVE (list, list_element); \ 416 } \ 417} 418 419/***********************************************************************/ 420/* 421 * R P C _ L I S T _ R E M O V E _ T A I L 422 * 423 * Remove the last entry from a list and return it. If the list is 424 * empty a NULL pointer is returned. 425 * 426 * Sample usage: 427 * 428 * rpc_list_t list; 429 * any_p_t list_element; 430 * 431 * RPC_LIST_REMOVE_TAIL (list, list_element, any_p_t); 432 */ 433 434#define RPC_LIST_REMOVE_TAIL(list, list_element, list_element_type) \ 435{ \ 436 if (RPC_LIST_EMPTY (list)) \ 437 { \ 438 list_element = NULL; \ 439 } \ 440 else \ 441 { \ 442 RPC_LIST_LAST (list, list_element, list_element_type); \ 443 RPC_LIST_REMOVE (list, list_element); \ 444 } \ 445} 446 447/***********************************************************************/ 448/* 449 * R P C _ L I S T _ E X T R A C T 450 * 451 * Remove the nth entry on a list and return it. 452 * If n exceeds the length of the list a NULL pointer is returned. 453 * 454 * Sample usage: 455 * 456 * rpc_list_t list; 457 * any_p_t list_element; 458 * 459 * RPC_LIST_EXTRACT (list, list_element, any_p_t, n); 460 */ 461 462#define RPC_LIST_EXTRACT(list, list_element, list_element_type, n) \ 463{ \ 464 RPC_LIST_LOOKUP (list, list_element, list_element_type, n); \ 465 if (list_element != NULL) \ 466 { \ 467 RPC_LIST_REMOVE (list, list_element); \ 468 } \ 469} 470 471/***********************************************************************/ 472/* 473 * R P C _ L I S T _ F I R S T 474 * 475 * Returns the first element in a list (without removing it). 476 * 477 * Sample usage: 478 * 479 * rpc_list_t list; 480 * any_p_t list_element; 481 * 482 * RPC_LIST_FIRST (list, list_element, any_p_t); 483 */ 484 485#define RPC_LIST_FIRST(list, list_element, list_element_type) \ 486 list_element = (list_element_type) (list.next); 487 488/***********************************************************************/ 489/* 490 * R P C _ L I S T _ L A S T 491 * 492 * Return the last element in a list (without removing it). 493 * 494 * Sample usage: 495 * 496 * rpc_list_t list; 497 * any_p_t list_element; 498 * 499 * RPC_LIST_LAST (list, list_element, any_p_t); 500 */ 501 502#define RPC_LIST_LAST(list, list_element, list_element_type) \ 503 list_element = (list_element_type) (list.last); 504 505/***********************************************************************/ 506/* 507 * R P C _ L I S T _ N E X T 508 * 509 * Can be used iteratively to walk a list and read all entries. 510 * When there are no more entries a NULL pointer is returned. 511 * 512 * Sample usage: 513 * 514 * any_p_t this_element; 515 * any_p_t next_element; 516 * 517 * RPC_LIST_NEXT (this_element, next_element, any_p_t); 518 */ 519 520#define RPC_LIST_NEXT(this_element, next_element, list_element_type) \ 521{ \ 522 if (((rpc_list_p_t) (this_element))->next == NULL) \ 523 { \ 524 next_element = NULL; \ 525 } \ 526 else \ 527 { \ 528 next_element = \ 529 (list_element_type) (((rpc_list_p_t) (this_element))->next); \ 530 } \ 531} 532 533/***********************************************************************/ 534/* 535 * R P C _ L I S T _ L O O K U P 536 * 537 * Get the nth entry on a list (without removing it). 538 * If n exceeds the length of the list a NULL pointer is returned. 539 * 540 * Sample usage: 541 * 542 * rpc_list_t list; 543 * any_p_t list_element; 544 * any_int n; 545 * 546 * RPC_LIST_LOOKUP (list, list_element, any_p_t, n); 547 */ 548 549#define RPC_LIST_LOOKUP(list, list_element, list_element_type, n) \ 550{ \ 551 int _count; \ 552\ 553 for (_count = (int) n, \ 554 list_element = (list_element_type) (list.next); \ 555 (_count > 1) && (list_element != NULL); \ 556 list_element = \ 557 (list_element_type) (((rpc_list_p_t) (list_element))->next), \ 558 _count--); \ 559} 560 561/***********************************************************************/ 562/* 563 * R P C _ L I S T _ C O U N T 564 * 565 * Return the number of entries on the list. 566 * 567 * Sample usage: 568 * 569 * rpc_list_t list; 570 * unsigned32 count; 571 * 572 * RPC_LIST_COUNT (list, count); 573 */ 574 575#define RPC_LIST_COUNT(list, count) \ 576{ \ 577 rpc_list_p_t _next_element;\ 578\ 579 for (count = 0, _next_element = ((rpc_list_p_t)(list.next));\ 580 _next_element != NULL;\ 581 count++, _next_element = ((rpc_list_p_t)(_next_element->next)));\ 582} 583 584/***********************************************************************/ 585/* 586 * R P C _ _ L I S T _ D E S C _ I N I T 587 * 588 */ 589 590PRIVATE void rpc__list_desc_init ( 591 rpc_list_desc_p_t /*list_desc*/, 592 unsigned32 /*max_size*/, 593 unsigned32 /*element_size*/, 594 unsigned32 /*element_type*/, 595 rpc_list_element_alloc_fn_t /*alloc_rtn*/, 596 rpc_list_element_free_fn_t /*free_rtn*/, 597 rpc_mutex_p_t /*mutex*/, 598 rpc_cond_p_t /*cond*/ 599 ); 600 601/***********************************************************************/ 602/* 603 * R P C _ _ L I S T _ E L E M E N T _ A L L O C 604 * 605 */ 606 607PRIVATE dce_pointer_t rpc__list_element_alloc ( 608 rpc_list_desc_p_t /*list_desc*/, 609 boolean32 /*block*/ 610 ); 611 612/***********************************************************************/ 613/* 614 * R P C _ _ L I S T _ E L E M E N T _ F R E E 615 * 616 */ 617 618PRIVATE void rpc__list_element_free ( 619 rpc_list_desc_p_t /*list_desc*/, 620 dce_pointer_t /*list_element*/ 621 ); 622 623/***********************************************************************/ 624/* 625 * R P C _ _ L I S T _ F O R K _ H A N D L E R 626 * 627 */ 628 629PRIVATE void rpc__list_fork_handler ( 630 rpc_fork_stage_id_t /*stage*/ 631 ); 632 633#endif /* _RPCLIST_H */ 634