1 /*------------------------------------------------------------------------- 2 * 3 * network_spgist.c 4 * SP-GiST support for network types. 5 * 6 * We split inet index entries first by address family (IPv4 or IPv6). 7 * If the entries below a given inner tuple are all of the same family, 8 * we identify their common prefix and split by the next bit of the address, 9 * and by whether their masklens exceed the length of the common prefix. 10 * 11 * An inner tuple that has both IPv4 and IPv6 children has a null prefix 12 * and exactly two nodes, the first being for IPv4 and the second for IPv6. 13 * mainnull14 * Otherwise, the prefix is a CIDR value representing the common prefix, 15 * and there are exactly four nodes. Node numbers 0 and 1 are for addresses 16 * with the same masklen as the prefix, while node numbers 2 and 3 are for 17 * addresses with larger masklen. (We do not allow a tuple to contain 18 * entries with masklen smaller than its prefix's.) Node numbers 0 and 1 19 * are distinguished by the next bit of the address after the common prefix, 20 * and likewise for node numbers 2 and 3. If there are no more bits in 21 * the address family, everything goes into node 0 (which will probably 22 * lead to creating an allTheSame tuple). 23 * 24 * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group 25 * Portions Copyright (c) 1994, Regents of the University of California 26 * 27 * IDENTIFICATION 28 * src/backend/utils/adt/network_spgist.c 29 * 30 *------------------------------------------------------------------------- 31 */ 32 #include "postgres.h" 33 34 #include <sys/socket.h> 35 36 #include "access/spgist.h" 37 #include "catalog/pg_type.h" 38 #include "utils/builtins.h" 39 #include "utils/inet.h" 40 41 42 static int inet_spg_node_number(const inet *val, int commonbits); 43 static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys, 44 ScanKey scankeys, bool leaf); 45 46 /* 47 * The SP-GiST configuration function 48 */ 49 Datum 50 inet_spg_config(PG_FUNCTION_ARGS) 51 { 52 /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */ 53 spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1); 54 55 cfg->prefixType = CIDROID; 56 cfg->labelType = VOIDOID; 57 cfg->canReturnData = true; 58 cfg->longValuesOK = false; 59 60 PG_RETURN_VOID(); 61 } 62 63 /* 64 * The SP-GiST choose function 65 */ 66 Datum 67 inet_spg_choose(PG_FUNCTION_ARGS) 68 { 69 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0); 70 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1); 71 inet *val = DatumGetInetPP(in->datum), 72 *prefix; 73 int commonbits; 74 75 /* 76 * If we're looking at a tuple that splits by address family, choose the 77 * appropriate subnode. 78 */ 79 if (!in->hasPrefix) 80 { 81 /* allTheSame isn't possible for such a tuple */ 82 Assert(!in->allTheSame); 83 Assert(in->nNodes == 2); 84 85 out->resultType = spgMatchNode; 86 out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1; 87 out->result.matchNode.restDatum = InetPGetDatum(val); 88 89 PG_RETURN_VOID(); 90 } 91 92 /* Else it must split by prefix */ 93 Assert(in->nNodes == 4 || in->allTheSame); 94 95 prefix = DatumGetInetPP(in->prefixDatum); 96 commonbits = ip_bits(prefix); 97 98 /* 99 * We cannot put addresses from different families under the same inner 100 * node, so we have to split if the new value's family is different. 101 */ 102 if (ip_family(val) != ip_family(prefix)) 103 { 104 /* Set up 2-node tuple */ 105 out->resultType = spgSplitTuple; 106 out->result.splitTuple.prefixHasPrefix = false; 107 out->result.splitTuple.prefixNNodes = 2; 108 out->result.splitTuple.prefixNodeLabels = NULL; 109 110 /* Identify which node the existing data goes into */ 111 out->result.splitTuple.childNodeN = 112 (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1; 113 114 out->result.splitTuple.postfixHasPrefix = true; 115 out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix); 116 117 PG_RETURN_VOID(); 118 } 119 120 /* 121 * If the new value does not match the existing prefix, we have to split. 122 */ 123 if (ip_bits(val) < commonbits || 124 bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0) 125 { 126 /* Determine new prefix length for the split tuple */ 127 commonbits = bitncommon(ip_addr(prefix), ip_addr(val), 128 Min(ip_bits(val), commonbits)); 129 130 /* Set up 4-node tuple */ 131 out->resultType = spgSplitTuple; 132 out->result.splitTuple.prefixHasPrefix = true; 133 out->result.splitTuple.prefixPrefixDatum = 134 InetPGetDatum(cidr_set_masklen_internal(val, commonbits)); 135 out->result.splitTuple.prefixNNodes = 4; 136 out->result.splitTuple.prefixNodeLabels = NULL; 137 138 /* Identify which node the existing data goes into */ 139 out->result.splitTuple.childNodeN = 140 inet_spg_node_number(prefix, commonbits); 141 142 out->result.splitTuple.postfixHasPrefix = true; 143 out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix); 144 145 PG_RETURN_VOID(); 146 } 147 148 /* 149 * All OK, choose the node to descend into. (If this tuple is marked 150 * allTheSame, the core code will ignore our choice of nodeN; but we need 151 * not account for that case explicitly here.) 152 */ 153 out->resultType = spgMatchNode; 154 out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits); 155 out->result.matchNode.restDatum = InetPGetDatum(val); 156 157 PG_RETURN_VOID(); 158 } 159 160 /* 161 * The GiST PickSplit method 162 */ 163 Datum 164 inet_spg_picksplit(PG_FUNCTION_ARGS) 165 { 166 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0); 167 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1); 168 inet *prefix, 169 *tmp; 170 int i, 171 commonbits; 172 bool differentFamilies = false; 173 174 /* Initialize the prefix with the first item */ 175 prefix = DatumGetInetPP(in->datums[0]); 176 commonbits = ip_bits(prefix); 177 178 /* Examine remaining items to discover minimum common prefix length */ 179 for (i = 1; i < in->nTuples; i++) 180 { 181 tmp = DatumGetInetPP(in->datums[i]); 182 183 if (ip_family(tmp) != ip_family(prefix)) 184 { 185 differentFamilies = true; 186 break; 187 } 188 189 if (ip_bits(tmp) < commonbits) 190 commonbits = ip_bits(tmp); 191 commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits); 192 if (commonbits == 0) 193 break; 194 } 195 196 /* Don't need labels; allocate output arrays */ 197 out->nodeLabels = NULL; 198 out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples); 199 out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples); 200 201 if (differentFamilies) 202 { 203 /* Set up 2-node tuple */ 204 out->hasPrefix = false; 205 out->nNodes = 2; 206 207 for (i = 0; i < in->nTuples; i++) 208 { 209 tmp = DatumGetInetPP(in->datums[i]); 210 out->mapTuplesToNodes[i] = 211 (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1; 212 out->leafTupleDatums[i] = InetPGetDatum(tmp); 213 } 214 } 215 else 216 { 217 /* Set up 4-node tuple */ 218 out->hasPrefix = true; 219 out->prefixDatum = 220 InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits)); 221 out->nNodes = 4; 222 223 for (i = 0; i < in->nTuples; i++) 224 { 225 tmp = DatumGetInetPP(in->datums[i]); 226 out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits); 227 out->leafTupleDatums[i] = InetPGetDatum(tmp); 228 } 229 } 230 231 PG_RETURN_VOID(); 232 } 233 234 /* 235 * The SP-GiST query consistency check for inner tuples 236 */ 237 Datum 238 inet_spg_inner_consistent(PG_FUNCTION_ARGS) 239 { 240 spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0); 241 spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1); 242 int i; 243 int which; 244 245 if (!in->hasPrefix) 246 { 247 Assert(!in->allTheSame); 248 Assert(in->nNodes == 2); 249 250 /* Identify which child nodes need to be visited */ 251 which = 1 | (1 << 1); 252 253 for (i = 0; i < in->nkeys; i++) 254 { 255 StrategyNumber strategy = in->scankeys[i].sk_strategy; 256 inet *argument = DatumGetInetPP(in->scankeys[i].sk_argument); 257 258 switch (strategy) 259 { 260 case RTLessStrategyNumber: 261 case RTLessEqualStrategyNumber: 262 if (ip_family(argument) == PGSQL_AF_INET) 263 which &= 1; 264 break; 265 266 case RTGreaterEqualStrategyNumber: 267 case RTGreaterStrategyNumber: 268 if (ip_family(argument) == PGSQL_AF_INET6) 269 which &= (1 << 1); 270 break; 271 272 case RTNotEqualStrategyNumber: 273 break; 274 275 default: 276 /* all other ops can only match addrs of same family */ 277 if (ip_family(argument) == PGSQL_AF_INET) 278 which &= 1; 279 else 280 which &= (1 << 1); 281 break; 282 } 283 } 284 } 285 else if (!in->allTheSame) 286 { 287 Assert(in->nNodes == 4); 288 289 /* Identify which child nodes need to be visited */ 290 which = inet_spg_consistent_bitmap(DatumGetInetPP(in->prefixDatum), 291 in->nkeys, in->scankeys, false); 292 } 293 else 294 { 295 /* Must visit all nodes; we assume there are less than 32 of 'em */ 296 which = ~0; 297 } 298 299 out->nNodes = 0; 300 301 if (which) 302 { 303 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); 304 305 for (i = 0; i < in->nNodes; i++) 306 { 307 if (which & (1 << i)) 308 { 309 out->nodeNumbers[out->nNodes] = i; 310 out->nNodes++; 311 } 312 } 313 } 314 315 PG_RETURN_VOID(); 316 } 317 318 /* 319 * The SP-GiST query consistency check for leaf tuples 320 */ 321 Datum 322 inet_spg_leaf_consistent(PG_FUNCTION_ARGS) 323 { 324 spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0); 325 spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1); 326 inet *leaf = DatumGetInetPP(in->leafDatum); 327 328 /* All tests are exact. */ 329 out->recheck = false; 330 331 /* Leaf is what it is... */ 332 out->leafValue = InetPGetDatum(leaf); 333 334 /* Use common code to apply the tests. */ 335 PG_RETURN_BOOL(inet_spg_consistent_bitmap(leaf, in->nkeys, in->scankeys, 336 true)); 337 } 338 339 /* 340 * Calculate node number (within a 4-node, single-family inner index tuple) 341 * 342 * The value must have the same family as the node's prefix, and 343 * commonbits is the mask length of the prefix. We use even or odd 344 * nodes according to the next address bit after the commonbits, 345 * and low or high nodes according to whether the value's mask length 346 * is larger than commonbits. 347 */ 348 static int 349 inet_spg_node_number(const inet *val, int commonbits) 350 { 351 int nodeN = 0; 352 353 if (commonbits < ip_maxbits(val) && 354 ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8))) 355 nodeN |= 1; 356 if (commonbits < ip_bits(val)) 357 nodeN |= 2; 358 359 return nodeN; 360 } 361 362 /* 363 * Calculate bitmap of node numbers that are consistent with the query 364 * 365 * This can be used either at a 4-way inner tuple, or at a leaf tuple. 366 * In the latter case, we should return a boolean result (0 or 1) 367 * not a bitmap. 368 * 369 * This definition is pretty odd, but the inner and leaf consistency checks 370 * are mostly common and it seems best to keep them in one function. 371 */ 372 static int 373 inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys, 374 bool leaf) 375 { 376 int bitmap; 377 int commonbits, 378 i; 379 380 /* Initialize result to allow visiting all children */ 381 if (leaf) 382 bitmap = 1; 383 else 384 bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3); 385 386 commonbits = ip_bits(prefix); 387 388 for (i = 0; i < nkeys; i++) 389 { 390 inet *argument = DatumGetInetPP(scankeys[i].sk_argument); 391 StrategyNumber strategy = scankeys[i].sk_strategy; 392 int order; 393 394 /* 395 * Check 0: different families 396 * 397 * Matching families do not help any of the strategies. 398 */ 399 if (ip_family(argument) != ip_family(prefix)) 400 { 401 switch (strategy) 402 { 403 case RTLessStrategyNumber: 404 case RTLessEqualStrategyNumber: 405 if (ip_family(argument) < ip_family(prefix)) 406 bitmap = 0; 407 break; 408 409 case RTGreaterEqualStrategyNumber: 410 case RTGreaterStrategyNumber: 411 if (ip_family(argument) > ip_family(prefix)) 412 bitmap = 0; 413 break; 414 415 case RTNotEqualStrategyNumber: 416 break; 417 418 default: 419 /* For all other cases, we can be sure there is no match */ 420 bitmap = 0; 421 break; 422 } 423 424 if (!bitmap) 425 break; 426 427 /* Other checks make no sense with different families. */ 428 continue; 429 } 430 431 /* 432 * Check 1: network bit count 433 * 434 * Network bit count (ip_bits) helps to check leaves for sub network 435 * and sup network operators. At non-leaf nodes, we know every child 436 * value has greater ip_bits, so we can avoid descending in some cases 437 * too. 438 * 439 * This check is less expensive than checking the address bits, so we 440 * are doing this before, but it has to be done after for the basic 441 * comparison strategies, because ip_bits only affect their results 442 * when the common network bits are the same. 443 */ 444 switch (strategy) 445 { 446 case RTSubStrategyNumber: 447 if (commonbits <= ip_bits(argument)) 448 bitmap &= (1 << 2) | (1 << 3); 449 break; 450 451 case RTSubEqualStrategyNumber: 452 if (commonbits < ip_bits(argument)) 453 bitmap &= (1 << 2) | (1 << 3); 454 break; 455 456 case RTSuperStrategyNumber: 457 if (commonbits == ip_bits(argument) - 1) 458 bitmap &= 1 | (1 << 1); 459 else if (commonbits >= ip_bits(argument)) 460 bitmap = 0; 461 break; 462 463 case RTSuperEqualStrategyNumber: 464 if (commonbits == ip_bits(argument)) 465 bitmap &= 1 | (1 << 1); 466 else if (commonbits > ip_bits(argument)) 467 bitmap = 0; 468 break; 469 470 case RTEqualStrategyNumber: 471 if (commonbits < ip_bits(argument)) 472 bitmap &= (1 << 2) | (1 << 3); 473 else if (commonbits == ip_bits(argument)) 474 bitmap &= 1 | (1 << 1); 475 else 476 bitmap = 0; 477 break; 478 } 479 480 if (!bitmap) 481 break; 482 483 /* 484 * Check 2: common network bits 485 * 486 * Compare available common prefix bits to the query, but not beyond 487 * either the query's netmask or the minimum netmask among the 488 * represented values. If these bits don't match the query, we can 489 * eliminate some cases. 490 */ 491 order = bitncmp(ip_addr(prefix), ip_addr(argument), 492 Min(commonbits, ip_bits(argument))); 493 494 if (order != 0) 495 { 496 switch (strategy) 497 { 498 case RTLessStrategyNumber: 499 case RTLessEqualStrategyNumber: 500 if (order > 0) 501 bitmap = 0; 502 break; 503 504 case RTGreaterEqualStrategyNumber: 505 case RTGreaterStrategyNumber: 506 if (order < 0) 507 bitmap = 0; 508 break; 509 510 case RTNotEqualStrategyNumber: 511 break; 512 513 default: 514 /* For all other cases, we can be sure there is no match */ 515 bitmap = 0; 516 break; 517 } 518 519 if (!bitmap) 520 break; 521 522 /* 523 * Remaining checks make no sense when common bits don't match. 524 */ 525 continue; 526 } 527 528 /* 529 * Check 3: next network bit 530 * 531 * We can filter out branch 2 or 3 using the next network bit of the 532 * argument, if it is available. 533 * 534 * This check matters for the performance of the search. The results 535 * would be correct without it. 536 */ 537 if (bitmap & ((1 << 2) | (1 << 3)) && 538 commonbits < ip_bits(argument)) 539 { 540 int nextbit; 541 542 nextbit = ip_addr(argument)[commonbits / 8] & 543 (1 << (7 - commonbits % 8)); 544 545 switch (strategy) 546 { 547 case RTLessStrategyNumber: 548 case RTLessEqualStrategyNumber: 549 if (!nextbit) 550 bitmap &= 1 | (1 << 1) | (1 << 2); 551 break; 552 553 case RTGreaterEqualStrategyNumber: 554 case RTGreaterStrategyNumber: 555 if (nextbit) 556 bitmap &= 1 | (1 << 1) | (1 << 3); 557 break; 558 559 case RTNotEqualStrategyNumber: 560 break; 561 562 default: 563 if (!nextbit) 564 bitmap &= 1 | (1 << 1) | (1 << 2); 565 else 566 bitmap &= 1 | (1 << 1) | (1 << 3); 567 break; 568 } 569 570 if (!bitmap) 571 break; 572 } 573 574 /* 575 * Remaining checks are only for the basic comparison strategies. This 576 * test relies on the strategy number ordering defined in stratnum.h. 577 */ 578 if (strategy < RTEqualStrategyNumber || 579 strategy > RTGreaterEqualStrategyNumber) 580 continue; 581 582 /* 583 * Check 4: network bit count 584 * 585 * At this point, we know that the common network bits of the prefix 586 * and the argument are the same, so we can go forward and check the 587 * ip_bits. 588 */ 589 switch (strategy) 590 { 591 case RTLessStrategyNumber: 592 case RTLessEqualStrategyNumber: 593 if (commonbits == ip_bits(argument)) 594 bitmap &= 1 | (1 << 1); 595 else if (commonbits > ip_bits(argument)) 596 bitmap = 0; 597 break; 598 599 case RTGreaterEqualStrategyNumber: 600 case RTGreaterStrategyNumber: 601 if (commonbits < ip_bits(argument)) 602 bitmap &= (1 << 2) | (1 << 3); 603 break; 604 } 605 606 if (!bitmap) 607 break; 608 609 /* Remaining checks don't make sense with different ip_bits. */ 610 if (commonbits != ip_bits(argument)) 611 continue; 612 613 /* 614 * Check 5: next host bit 615 * 616 * We can filter out branch 0 or 1 using the next host bit of the 617 * argument, if it is available. 618 * 619 * This check matters for the performance of the search. The results 620 * would be correct without it. There is no point in running it for 621 * leafs as we have to check the whole address on the next step. 622 */ 623 if (!leaf && bitmap & (1 | (1 << 1)) && 624 commonbits < ip_maxbits(argument)) 625 { 626 int nextbit; 627 628 nextbit = ip_addr(argument)[commonbits / 8] & 629 (1 << (7 - commonbits % 8)); 630 631 switch (strategy) 632 { 633 case RTLessStrategyNumber: 634 case RTLessEqualStrategyNumber: 635 if (!nextbit) 636 bitmap &= 1 | (1 << 2) | (1 << 3); 637 break; 638 639 case RTGreaterEqualStrategyNumber: 640 case RTGreaterStrategyNumber: 641 if (nextbit) 642 bitmap &= (1 << 1) | (1 << 2) | (1 << 3); 643 break; 644 645 case RTNotEqualStrategyNumber: 646 break; 647 648 default: 649 if (!nextbit) 650 bitmap &= 1 | (1 << 2) | (1 << 3); 651 else 652 bitmap &= (1 << 1) | (1 << 2) | (1 << 3); 653 break; 654 } 655 656 if (!bitmap) 657 break; 658 } 659 660 /* 661 * Check 6: whole address 662 * 663 * This is the last check for correctness of the basic comparison 664 * strategies. It's only appropriate at leaf entries. 665 */ 666 if (leaf) 667 { 668 /* Redo ordering comparison using all address bits */ 669 order = bitncmp(ip_addr(prefix), ip_addr(argument), 670 ip_maxbits(prefix)); 671 672 switch (strategy) 673 { 674 case RTLessStrategyNumber: 675 if (order >= 0) 676 bitmap = 0; 677 break; 678 679 case RTLessEqualStrategyNumber: 680 if (order > 0) 681 bitmap = 0; 682 break; 683 684 case RTEqualStrategyNumber: 685 if (order != 0) 686 bitmap = 0; 687 break; 688 689 case RTGreaterEqualStrategyNumber: 690 if (order < 0) 691 bitmap = 0; 692 break; 693 694 case RTGreaterStrategyNumber: 695 if (order <= 0) 696 bitmap = 0; 697 break; 698 699 case RTNotEqualStrategyNumber: 700 if (order == 0) 701 bitmap = 0; 702 break; 703 } 704 705 if (!bitmap) 706 break; 707 } 708 } 709 710 return bitmap; 711 } 712