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