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 *
14 * 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-2019, 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
42static int inet_spg_node_number(const inet *val, int commonbits);
43static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys,
44 ScanKey scankeys, bool leaf);
45
46/*
47 * The SP-GiST configuration function
48 */
49Datum
50inet_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 */
66Datum
67inet_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 */
163Datum
164inet_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 */
237Datum
238inet_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 */
321Datum
322inet_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 */
348static int
349inet_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 */
372static int
373inet_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