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