1 /* $NetBSD: prop_number.c,v 1.22 2009/03/15 22:29:11 cegger Exp $ */ 2 3 /*- 4 * Copyright (c) 2006 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #include <libprop/prop_number.h> 33 #include "prop_object_impl.h" 34 #include "prop_rb_impl.h" 35 36 #if defined(_KERNEL) 37 #include <sys/systm.h> 38 #define strtoll strtoq 39 #define strtoull strtouq 40 #define sprintf ksprintf 41 #elif defined(_STANDALONE) 42 #include <sys/param.h> 43 #include <lib/libkern/libkern.h> 44 #else 45 #include <errno.h> 46 #include <stdlib.h> 47 #endif 48 49 struct _prop_number { 50 struct _prop_object pn_obj; 51 struct rb_node pn_link; 52 struct _prop_number_value { 53 union { 54 int64_t pnu_signed; 55 uint64_t pnu_unsigned; 56 } pnv_un; 57 #define pnv_signed pnv_un.pnu_signed 58 #define pnv_unsigned pnv_un.pnu_unsigned 59 unsigned int pnv_is_unsigned :1, 60 :31; 61 } pn_value; 62 }; 63 64 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr"); 65 66 static _prop_object_free_rv_t 67 _prop_number_free(prop_stack_t, prop_object_t *); 68 static bool _prop_number_externalize( 69 struct _prop_object_externalize_context *, 70 void *); 71 static _prop_object_equals_rv_t 72 _prop_number_equals(prop_object_t, prop_object_t, 73 void **, void **, 74 prop_object_t *, prop_object_t *); 75 76 static void _prop_number_lock(void); 77 static void _prop_number_unlock(void); 78 79 static const struct _prop_object_type _prop_object_type_number = { 80 .pot_type = PROP_TYPE_NUMBER, 81 .pot_free = _prop_number_free, 82 .pot_extern = _prop_number_externalize, 83 .pot_equals = _prop_number_equals, 84 .pot_lock = _prop_number_lock, 85 .pot_unlock = _prop_number_unlock, 86 }; 87 88 #define prop_object_is_number(x) \ 89 ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number) 90 91 /* 92 * Number objects are immutable, and we are likely to have many number 93 * objects that have the same value. So, to save memory, we unique'ify 94 * numbers so we only have one copy of each. 95 */ 96 97 static int 98 _prop_number_compare_values(const struct _prop_number_value *pnv1, 99 const struct _prop_number_value *pnv2) 100 { 101 102 /* Signed numbers are sorted before unsigned numbers. */ 103 104 if (pnv1->pnv_is_unsigned) { 105 if (! pnv2->pnv_is_unsigned) 106 return (1); 107 if (pnv1->pnv_unsigned < pnv2->pnv_unsigned) 108 return (-1); 109 if (pnv1->pnv_unsigned > pnv2->pnv_unsigned) 110 return (1); 111 return (0); 112 } 113 114 if (pnv2->pnv_is_unsigned) 115 return (-1); 116 if (pnv1->pnv_signed < pnv2->pnv_signed) 117 return (-1); 118 if (pnv1->pnv_signed > pnv2->pnv_signed) 119 return (1); 120 return (0); 121 } 122 123 static int 124 /*ARGSUSED*/ 125 _prop_number_rb_compare_nodes(void *ctx __unused, 126 const void *n1, const void *n2) 127 { 128 const struct _prop_number *pn1 = n1; 129 const struct _prop_number *pn2 = n2; 130 131 return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value); 132 } 133 134 static int 135 /*ARGSUSED*/ 136 _prop_number_rb_compare_key(void *ctx __unused, const void *n, const void *v) 137 { 138 const struct _prop_number *pn = n; 139 const struct _prop_number_value *pnv = v; 140 141 return _prop_number_compare_values(&pn->pn_value, pnv); 142 } 143 144 static const rb_tree_ops_t _prop_number_rb_tree_ops = { 145 .rbto_compare_nodes = _prop_number_rb_compare_nodes, 146 .rbto_compare_key = _prop_number_rb_compare_key, 147 .rbto_node_offset = offsetof(struct _prop_number, pn_link), 148 .rbto_context = NULL 149 }; 150 151 static struct rb_tree _prop_number_tree; 152 _PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex) 153 154 /* ARGSUSED */ 155 static _prop_object_free_rv_t 156 _prop_number_free(prop_stack_t stack, prop_object_t *obj) 157 { 158 prop_number_t pn = *obj; 159 160 _prop_rb_tree_remove_node(&_prop_number_tree, pn); 161 162 _PROP_POOL_PUT(_prop_number_pool, pn); 163 164 return (_PROP_OBJECT_FREE_DONE); 165 } 166 167 _PROP_ONCE_DECL(_prop_number_init_once) 168 169 static int 170 _prop_number_init(void) 171 { 172 173 _PROP_MUTEX_INIT(_prop_number_tree_mutex); 174 _prop_rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops); 175 return 0; 176 } 177 178 static void 179 _prop_number_lock(void) 180 { 181 /* XXX: init necessary? */ 182 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init); 183 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 184 } 185 186 static void 187 _prop_number_unlock(void) 188 { 189 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 190 } 191 192 static bool 193 _prop_number_externalize(struct _prop_object_externalize_context *ctx, 194 void *v) 195 { 196 prop_number_t pn = v; 197 char tmpstr[32]; 198 199 /* 200 * For unsigned numbers, we output in hex. For signed numbers, 201 * we output in decimal. 202 */ 203 if (pn->pn_value.pnv_is_unsigned) 204 sprintf(tmpstr, "0x%" PRIx64, pn->pn_value.pnv_unsigned); 205 else 206 sprintf(tmpstr, "%" PRIi64, pn->pn_value.pnv_signed); 207 208 if (_prop_object_externalize_start_tag(ctx, "integer") == false || 209 _prop_object_externalize_append_cstring(ctx, tmpstr) == false || 210 _prop_object_externalize_end_tag(ctx, "integer") == false) 211 return (false); 212 213 return (true); 214 } 215 216 /* ARGSUSED */ 217 static _prop_object_equals_rv_t 218 _prop_number_equals(prop_object_t v1, prop_object_t v2, 219 void **stored_pointer1, void **stored_pointer2, 220 prop_object_t *next_obj1, prop_object_t *next_obj2) 221 { 222 prop_number_t num1 = v1; 223 prop_number_t num2 = v2; 224 225 /* 226 * There is only ever one copy of a number object at any given 227 * time, so we can reduce this to a simple pointer equality check 228 * in the common case. 229 */ 230 if (num1 == num2) 231 return (_PROP_OBJECT_EQUALS_TRUE); 232 233 /* 234 * If the numbers are the same signed-ness, then we know they 235 * cannot be equal because they would have had pointer equality. 236 */ 237 if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned) 238 return (_PROP_OBJECT_EQUALS_FALSE); 239 240 /* 241 * We now have one signed value and one unsigned value. We can 242 * compare them iff: 243 * - The unsigned value is not larger than the signed value 244 * can represent. 245 * - The signed value is not smaller than the unsigned value 246 * can represent. 247 */ 248 if (num1->pn_value.pnv_is_unsigned) { 249 /* 250 * num1 is unsigned and num2 is signed. 251 */ 252 if (num1->pn_value.pnv_unsigned > INT64_MAX) 253 return (_PROP_OBJECT_EQUALS_FALSE); 254 if (num2->pn_value.pnv_signed < 0) 255 return (_PROP_OBJECT_EQUALS_FALSE); 256 } else { 257 /* 258 * num1 is signed and num2 is unsigned. 259 */ 260 if (num1->pn_value.pnv_signed < 0) 261 return (_PROP_OBJECT_EQUALS_FALSE); 262 if (num2->pn_value.pnv_unsigned > INT64_MAX) 263 return (_PROP_OBJECT_EQUALS_FALSE); 264 } 265 266 if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed) 267 return _PROP_OBJECT_EQUALS_TRUE; 268 else 269 return _PROP_OBJECT_EQUALS_FALSE; 270 } 271 272 static prop_number_t 273 _prop_number_alloc(const struct _prop_number_value *pnv) 274 { 275 prop_number_t opn, pn, rpn; 276 277 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init); 278 279 /* 280 * Check to see if this already exists in the tree. If it does, 281 * we just retain it and return it. 282 */ 283 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 284 opn = _prop_rb_tree_find(&_prop_number_tree, pnv); 285 if (opn != NULL) { 286 prop_object_retain(opn); 287 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 288 return (opn); 289 } 290 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 291 292 /* 293 * Not in the tree. Create it now. 294 */ 295 296 pn = _PROP_POOL_GET(_prop_number_pool); 297 if (pn == NULL) 298 return (NULL); 299 300 _prop_object_init(&pn->pn_obj, &_prop_object_type_number); 301 302 pn->pn_value = *pnv; 303 304 /* 305 * We dropped the mutex when we allocated the new object, so 306 * we have to check again if it is in the tree. 307 */ 308 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 309 opn = _prop_rb_tree_find(&_prop_number_tree, pnv); 310 if (opn != NULL) { 311 prop_object_retain(opn); 312 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 313 _PROP_POOL_PUT(_prop_number_pool, pn); 314 return (opn); 315 } 316 rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn); 317 _PROP_ASSERT(rpn == pn); 318 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 319 return (pn); 320 } 321 322 /* 323 * prop_number_create_integer -- 324 * Create a prop_number_t and initialize it with the 325 * provided integer value. 326 */ 327 prop_number_t 328 prop_number_create_integer(int64_t val) 329 { 330 struct _prop_number_value pnv; 331 332 memset(&pnv, 0, sizeof(pnv)); 333 pnv.pnv_signed = val; 334 pnv.pnv_is_unsigned = false; 335 336 return (_prop_number_alloc(&pnv)); 337 } 338 339 /* 340 * prop_number_create_unsigned_integer -- 341 * Create a prop_number_t and initialize it with the 342 * provided unsigned integer value. 343 */ 344 prop_number_t 345 prop_number_create_unsigned_integer(uint64_t val) 346 { 347 struct _prop_number_value pnv; 348 349 memset(&pnv, 0, sizeof(pnv)); 350 pnv.pnv_unsigned = val; 351 pnv.pnv_is_unsigned = true; 352 353 return (_prop_number_alloc(&pnv)); 354 } 355 356 /* 357 * prop_number_copy -- 358 * Copy a prop_number_t. 359 */ 360 prop_number_t 361 prop_number_copy(prop_number_t opn) 362 { 363 364 if (! prop_object_is_number(opn)) 365 return (NULL); 366 367 /* 368 * Because we only ever allocate one object for any given 369 * value, this can be reduced to a simple retain operation. 370 */ 371 prop_object_retain(opn); 372 return (opn); 373 } 374 375 /* 376 * prop_number_unsigned -- 377 * Returns true if the prop_number_t has an unsigned value. 378 */ 379 bool 380 prop_number_unsigned(prop_number_t pn) 381 { 382 383 return (pn->pn_value.pnv_is_unsigned); 384 } 385 386 /* 387 * prop_number_size -- 388 * Return the size, in bits, required to hold the value of 389 * the specified number. 390 */ 391 int 392 prop_number_size(prop_number_t pn) 393 { 394 struct _prop_number_value *pnv; 395 396 if (! prop_object_is_number(pn)) 397 return (0); 398 399 pnv = &pn->pn_value; 400 401 if (pnv->pnv_is_unsigned) { 402 if (pnv->pnv_unsigned > UINT32_MAX) 403 return (64); 404 if (pnv->pnv_unsigned > UINT16_MAX) 405 return (32); 406 if (pnv->pnv_unsigned > UINT8_MAX) 407 return (16); 408 return (8); 409 } 410 411 if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN) 412 return (64); 413 if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN) 414 return (32); 415 if (pnv->pnv_signed > INT8_MAX || pnv->pnv_signed < INT8_MIN) 416 return (16); 417 return (8); 418 } 419 420 /* 421 * prop_number_integer_value -- 422 * Get the integer value of a prop_number_t. 423 */ 424 int64_t 425 prop_number_integer_value(prop_number_t pn) 426 { 427 428 /* 429 * XXX Impossible to distinguish between "not a prop_number_t" 430 * XXX and "prop_number_t has a value of 0". 431 */ 432 if (! prop_object_is_number(pn)) 433 return (0); 434 435 return (pn->pn_value.pnv_signed); 436 } 437 438 /* 439 * prop_number_unsigned_integer_value -- 440 * Get the unsigned integer value of a prop_number_t. 441 */ 442 uint64_t 443 prop_number_unsigned_integer_value(prop_number_t pn) 444 { 445 446 /* 447 * XXX Impossible to distinguish between "not a prop_number_t" 448 * XXX and "prop_number_t has a value of 0". 449 */ 450 if (! prop_object_is_number(pn)) 451 return (0); 452 453 return (pn->pn_value.pnv_unsigned); 454 } 455 456 /* 457 * prop_number_equals -- 458 * Return true if two numbers are equivalent. 459 */ 460 bool 461 prop_number_equals(prop_number_t num1, prop_number_t num2) 462 { 463 if (!prop_object_is_number(num1) || !prop_object_is_number(num2)) 464 return (false); 465 466 return (prop_object_equals(num1, num2)); 467 } 468 469 /* 470 * prop_number_equals_integer -- 471 * Return true if the number is equivalent to the specified integer. 472 */ 473 bool 474 prop_number_equals_integer(prop_number_t pn, int64_t val) 475 { 476 477 if (! prop_object_is_number(pn)) 478 return (false); 479 480 if (pn->pn_value.pnv_is_unsigned && 481 (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0)) 482 return (false); 483 484 return (pn->pn_value.pnv_signed == val); 485 } 486 487 /* 488 * prop_number_equals_unsigned_integer -- 489 * Return true if the number is equivalent to the specified 490 * unsigned integer. 491 */ 492 bool 493 prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val) 494 { 495 496 if (! prop_object_is_number(pn)) 497 return (false); 498 499 if (! pn->pn_value.pnv_is_unsigned && 500 (pn->pn_value.pnv_signed < 0 || val > INT64_MAX)) 501 return (false); 502 503 return (pn->pn_value.pnv_unsigned == val); 504 } 505 506 static bool 507 _prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx, 508 struct _prop_number_value *pnv) 509 { 510 char *cp; 511 512 _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) == 513 sizeof(uint64_t)); 514 515 #ifndef _KERNEL 516 errno = 0; 517 #endif 518 pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0); 519 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */ 520 if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE) 521 return (false); 522 #endif 523 pnv->pnv_is_unsigned = true; 524 ctx->poic_cp = cp; 525 526 return (true); 527 } 528 529 static bool 530 _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx, 531 struct _prop_number_value *pnv) 532 { 533 char *cp; 534 535 _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t)); 536 537 #ifndef _KERNEL 538 errno = 0; 539 #endif 540 pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0); 541 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */ 542 if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) && 543 errno == ERANGE) 544 return (false); 545 #endif 546 pnv->pnv_is_unsigned = false; 547 ctx->poic_cp = cp; 548 549 return (true); 550 } 551 552 /* 553 * _prop_number_internalize -- 554 * Parse a <number>...</number> and return the object created from 555 * the external representation. 556 */ 557 /* ARGSUSED */ 558 bool 559 _prop_number_internalize(prop_stack_t stack, prop_object_t *obj, 560 struct _prop_object_internalize_context *ctx) 561 { 562 struct _prop_number_value pnv; 563 564 memset(&pnv, 0, sizeof(pnv)); 565 566 /* No attributes, no empty elements. */ 567 if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element) 568 return (true); 569 570 /* 571 * If the first character is '-', then we treat as signed. 572 * If the first two characters are "0x" (i.e. the number is 573 * in hex), then we treat as unsigned. Otherwise, we try 574 * signed first, and if that fails (presumably due to ERANGE), 575 * then we switch to unsigned. 576 */ 577 if (ctx->poic_cp[0] == '-') { 578 if (_prop_number_internalize_signed(ctx, &pnv) == false) 579 return (true); 580 } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') { 581 if (_prop_number_internalize_unsigned(ctx, &pnv) == false) 582 return (true); 583 } else { 584 if (_prop_number_internalize_signed(ctx, &pnv) == false && 585 _prop_number_internalize_unsigned(ctx, &pnv) == false) 586 return (true); 587 } 588 589 if (_prop_object_internalize_find_tag(ctx, "integer", 590 _PROP_TAG_TYPE_END) == false) 591 return (true); 592 593 *obj = _prop_number_alloc(&pnv); 594 return (true); 595 } 596