PostgreSQL expanding cidr into individual addresses

Question

I have a large list of subnets in a network stored in the following layout. This is used as a master table to store assets that will be used to automatically probe for status by a Python-script at regular intervals.

CREATE TEMP TABLE tmp_networks (
    network cidr PRIMARY KEY
);

Lets assume its filled with these values for the sake of demonstration:

• 10.0.0.0/8
• 10.0.1.0/24
• 192.168.0.0/24

When I run the script, the Python-script will execute the following query to remove any overlaps:

SELECT network
    FROM tmp_networks
    WHERE NOT EXISTS (
        SELECT network
        FROM tmp_networks n
        WHERE n.network >> tmp_networks.network
);

This works great, except for one tiny issue; I also have a list of individual addresses that should be excluded from the job. This is also a table in the database:

CREATE TEMP TABLE tmp_except (
    address inet PRIMARY KEY
);

Lets assume this contains the following addresses:

• 10.0.0.100
• 192.168.0.10

Now, I have failed to find a good method to remove these spesific addresses from the database output. In my thoughts, the solution would be something like:

• select all subnets
• if any exception address is found within the subnet, split the subnet into smaller pieces until the single exception address can be removed and all other addresses remain

I have tried to investigate whether something like this is possible to do in pure PostgreSQL, but have failed to find any way to solve this. Any pointers as to how this should be solved?

Answer 1

I would approach this with two functions. The first function takes a cidr and an exception address, and returns a set of cidrs which are equivalent to the original cidr minus the exception address. The function works by splitting the cidr into two halves, and then recursively removing the exception address from the half it is in. More sophisticated algorithm could avoid some of the unnecessary splits. The simple function looks like this:

CREATE OR REPLACE FUNCTION split_cidr(net cidr, exc inet) returns setof cidr language plpgsql AS $$
DECLARE
  r cidr;
  lower cidr;
  upper cidr;
BEGIN
  IF masklen(net) >= 32 THEN RETURN; END IF;
  lower = set_masklen(net, masklen(net)+1);
  upper = set_masklen( (lower | ~ netmask(lower)) + 1, masklen(lower));
  IF exc << upper THEN
    RETURN NEXT lower;
    FOR r IN SELECT * from split_cidr(upper, exc)
    LOOP RETURN NEXT r;
    END LOOP;
  ELSE
    FOR r IN SELECT * from split_cidr(lower, exc)
    LOOP RETURN NEXT r;
    END LOOP;
    RETURN NEXT upper;
  END IF;
  RETURN;
END $$;

Armed with this function, one could then iterate through the network list applying it to those networks that contained an exception address. The following function splits the list of network addresses into those that contain exceptions and those that don't. Those that don't are returned, those that do have the above function applied. This does not deal with the case where a network contains more than exception address.

CREATE OR REPLACE FUNCTION DOIT() RETURNS Setof cidr  language plpgsql AS $$
DECLARE
 r cidr;
 x cidr;
 z inet;
BEGIN
 -- these are the rows where the network has no exceptions
 FOR r in SELECT network FROM tmp_networks n WHERE NOT EXISTS (
   SELECT address FROM tmp_except WHERE address << n.network )
 LOOP RETURN NEXT r;
 END LOOP;

 -- these are the rows where the network has an exception
 FOR r,z in SELECT network, address from tmp_networks full join tmp_except on true where address << network
 LOOP
   FOR x IN SELECT * FROM split_cidr(r, z)
   LOOP RETURN NEXT x;
   END LOOP;
 END LOOP;
END $$;

I would approach the case of multiple exception addresses per network by modifying split_cidr to take an array of exception addresses rather than a single exception address, and then aggregating the exceptions for each network into an array and calling split_cidr_array for the network and its array of exceptions.