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