NAPI-434

For DOCKER-723, we have found ourselves wanting a way for NAPI to automatically generate a network for a user's fabric, using an unallocated subnet. We'll want to discuss what this interface should provide, but it should probably only allow allocations inside the RFC 1918 address space, and it should probably allow for specifying the requested subnet size.

Former user commented on 2017-11-06T17:37:24.560-0500 (edited 2017-11-30T19:56:58.717-0500):

We have 2 problems to solve. First, we want to change NAPI so that it no longer prevents us from setting the vlan_id to 1. Second, we want to modify NAPI so that, it no longer requires the user to specify a subnet when creating a network – this will necessitate automatically allocating a free subnet.

So, for vlan_id , we want to see where it is that we do a vlan_id check.

[...SNIPPED 164 LINES...]
lib/util/validate.js   validateVLAN{}/ 2
lib/util/validate.js   validateVLAN{}/Number()/ 1
[...SNIPPED 3 LINES...]

Skimming the long output of the above blip command, the above 2 validate-paths caught my eye. Let's take a look at them.

] ./blip index-get-subtrees-str validateVLAN{}/ 
lib/util/validate.js:

function validateVLAN(_, name, vlan_id, callback) 
{
	var id = Number(vlan_id);
	if (isNaN(id) || id < 0 || id === 1 || id > 4094) {
		return callback(errors.invalidParam(name, constants.VLAN_MSG));
	}
	return callback(null, id);
}

We can see that if the id === 1 we return an error. We can easily fix this by remove that boolean check.

So, we can now move on to the subnet auto-allocation problem.

We want to find where we validate the parameters that we pass to the network-creation code path. By convention name the object that specifies how to carry out a validation something like CREATE_SCHEMA or LIST_SCHEMA or DELETE_SCHEMA . So let's try searching for that.

] ./blip index-word-count CREATE_SCHEMA 
lib/models/aggregation.js   createAggr{}/ 1
lib/models/aggregation.js   createAggr{}/params()/ 1
lib/models/ip/index.js   createIP{}/ 1
lib/models/ip/index.js   createIP{}/params()/ 1
lib/models/network-pool.js   createNetworkPool{}/ 1
lib/models/network-pool.js   createNetworkPool{}/params()/ 1
lib/models/network.js   createValidNetwork{}/ 1
lib/models/network.js   createValidNetwork{}/params()/ 1
lib/models/nic-tag.js   createNicTag{}/ 1
lib/models/nic-tag.js   createNicTag{}/params()/ 1
lib/models/nic/create.js   validateParams{}/ 1
lib/models/nic/create.js   validateParams{}/params()/ 1
lib/models/vlan.js   createFabricVLAN{}/ 1
lib/models/vlan.js   createFabricVLAN{}/params()/ 1

We can see that the function that calls the validators is intuitively named createValidNetwork . Let's get a bird-eye-view of that function.

] ./blip index-prefix createValidNetwork{}/ 
lib/models/network.js:

createValidNetwork{}/
createValidNetwork{}/params()/
createValidNetwork{}/params()/function{}/
createValidNetwork{}/params()/function{}/callback()/
createValidNetwork{}/params()/function{}/callback()/
createValidNetwork{}/params()/function{}/callback()/Network()/

So, it pretty simply calls the validator's params function and if the validation succeeds, it creates a new Network object. Note that I can tell, because I helped create the validation library that's used under the hood, and know from prior experience that a call to Network is actually a constructor invocation. Let's look at this function just to be sure.

] ./blip index-get-subtrees-str createValidNetwork{}/ 
lib/models/network.js:

function createValidNetwork(opts, callback) 
{
	var app = opts.app;
	var log = opts.log;
	var params = opts.params;
	var copts = {
		app : app,
		fabric : opts.fabric,
		log : log,
		owner_uuid : opts.owner_uuid
	};
	validate.params(CREATE_SCHEMA, copts, params, <<< function{}/ >>>);
}

] ./blip index-get-subtrees-str createValidNetwork{}/params()/function{}/ 
lib/models/network.js:

function (err, validatedParams) 
{
	if (err) {
		return callback(err);
	}
	validatedParams.ip_use_strings = true;
	if (validatedParams.fabric && validatedParams.internet_nat &&
	    !validatedParams.gateway) {
		validatedParams.gateway = validatedParams.provision_start_ip;
	}
	return callback(null, new Network(validatedParams));
}

Let's see where createValidNetwork is called.

] ./blip index-prefix createValidNetwork up 
lib/models/network.js:

createValidNetwork{}/
createValidNetwork()/_createNetObj{}/pipeline()/createNetwork{}/

We see that createValidNetwork is called by createNetwork , as part of a vasync pipeline. Let's get closer and look at that pipeline:

] ./blip index-prefix createNetwork{}/pipeline()/ down 
lib/models/network.js:

createNetwork{}/pipeline()/
createNetwork{}/pipeline()/_createNetObj{}/
createNetwork{}/pipeline()/_createNetObj{}/createValidNetwork()/
createNetwork{}/pipeline()/_createNetObj{}/createValidNetwork()/function{}/
createNetwork{}/pipeline()/_createNetObj{}/createValidNetwork()/function{}/cb()/
createNetwork{}/pipeline()/_createNetObj{}/createValidNetwork()/function{}/cb()/
createNetwork{}/pipeline()/_createNet{}/
createNetwork{}/pipeline()/_createNet{}/raw()/
createNetwork{}/pipeline()/_createNet{}/debug()/
createNetwork{}/pipeline()/_createNet{}/putObject()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/error()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/hasCauseWithName()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/cb()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/cb()/InvalidParamsError()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/cb()/InvalidParamsError()/duplicateParam()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/cb()/
createNetwork{}/pipeline()/_createNet{}/putObject()/function{}/cb()/
createNetwork{}/pipeline()/_createIPbucket{}/
createNetwork{}/pipeline()/_createIPbucket{}/bucketInit()/
createNetwork{}/pipeline()/_createIPs{}/
createNetwork{}/pipeline()/_createIPs{}/toString()/
createNetwork{}/pipeline()/_createIPs{}/userReservedIP()/
createNetwork{}/pipeline()/_createIPs{}/toString()/
createNetwork{}/pipeline()/_createIPs{}/adminReservedIP()/
createNetwork{}/pipeline()/_createIPs{}/contains()/
createNetwork{}/pipeline()/_createIPs{}/hasOwnProperty()/
createNetwork{}/pipeline()/_createIPs{}/hasOwnProperty()/toString()/
createNetwork{}/pipeline()/_createIPs{}/toString()/
createNetwork{}/pipeline()/_createIPs{}/adminReservedIP()/
createNetwork{}/pipeline()/_createIPs{}/broadcast()/
createNetwork{}/pipeline()/_createIPs{}/hasOwnProperty()/
createNetwork{}/pipeline()/_createIPs{}/hasOwnProperty()/toString()/
createNetwork{}/pipeline()/_createIPs{}/toString()/
createNetwork{}/pipeline()/_createIPs{}/adminReservedIP()/
createNetwork{}/pipeline()/_createIPs{}/ipAddrMinus()/
createNetwork{}/pipeline()/_createIPs{}/ipAddrPlus()/
createNetwork{}/pipeline()/_createIPs{}/forEach()/
createNetwork{}/pipeline()/_createIPs{}/forEach()/function{}/
createNetwork{}/pipeline()/_createIPs{}/forEach()/function{}/hasOwnProperty()/
createNetwork{}/pipeline()/_createIPs{}/forEach()/function{}/placeholderIP()/
createNetwork{}/pipeline()/_createIPs{}/keys()/
createNetwork{}/pipeline()/_createIPs{}/sort()/
createNetwork{}/pipeline()/_createIPs{}/map()/
createNetwork{}/pipeline()/_createIPs{}/map()/function{}/
createNetwork{}/pipeline()/_createIPs{}/info()/
createNetwork{}/pipeline()/_createIPs{}/batchCreate()/
createNetwork{}/pipeline()/function{}/
createNetwork{}/pipeline()/function{}/callback()/
createNetwork{}/pipeline()/function{}/callback()/

This output is a bit overwhelming, but can see that we do 4 things . Looking at the above paths, it looks like we construct the object in memory, before uploading it to Moray via the putObject function. We then create a moray bucket for IPs, and create and upload those IPs in a single call to _createIPs (given away by the call to batchCreate . We probably have to do it in one call so that we can determine which IPs are not already taken.

So, let's take a quick look at batchCreate to see what it actually does.

] ./blip index-prefix batchCreate 
lib/models/ip/index.js:

batchCreateIPs{}/
batchCreateIPs{}/debug()/
batchCreateIPs{}/getBucketObj()/
batchCreateIPs{}/map()/
batchCreateIPs{}/map()/function{}/
batchCreateIPs{}/map()/function{}/IP()/
batchCreateIPs{}/map()/function{}/push()/
batchCreateIPs{}/map()/function{}/key()/
batchCreateIPs{}/map()/function{}/raw()/
batchCreateIPs{}/info()/
batchCreateIPs{}/batch()/
batchCreateIPs{}/batch()/function{}/
batchCreateIPs{}/batch()/function{}/callback()/
batchCreateIPs{}/batch()/function{}/callback()/

Not quite what we were expecting, my guess is that batchCreateIPs is exported as batchCreate . We will confirm this next. Note the call to batch near the end.

] ./blip exports-what lib/models/ip/index.js 
(batchCreate BUCKET bucket bucketInit bucketName create createUpdated del get
  key IP list nextIPonNetwork params update)

Indeed it is exported under a different name. So, we see where the validation happens and have a rough idea of how it happens. It seems that we will want to insert our subnet allocation code in that createNetwork function's pipeline. Since we want to optionally auto-allocate subnets, we want to check out where NAPI handles subnets in its code.

] ./blip index-word-count subnet 
lib/endpoints/networks/ips.js   validateIP{}/ 1
lib/endpoints/search.js   _transform=/ 1
lib/endpoints/search.js   _transform=/function{}/ 1
lib/init.js   initNetwork{}/ 1
lib/models/network.js   validateImmutableFields{}/ 2
lib/models/network.js   validateImmutableFields{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/ 12
lib/models/network.js   validateProvisionRange{}/ok()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/compare()/ 1
lib/models/network.js   validateProvisionRange{}/fmt()/ 1
lib/models/network.js   validateProvisionRange{}/debug()/ 2
lib/models/network.js   validateRoutes{}/ 4
lib/models/network.js   validateRoutes{}/fmt()/ 2
lib/models/network.js   Network{}/ 9
lib/models/network.js   Network{}/ok()/ 1
lib/models/network.js   Network{}/createCIDR()/ 1
lib/models/network.js   Network{}/createCIDR()/ 1
lib/models/network.js   Network{}/ok()/ 1
lib/models/network.js   raw=/ 2
lib/models/network.js   raw=/networkRaw{}/ 2
lib/models/network.js   serialize=/ 2
lib/models/network.js   serialize=/networkSerialize{}/ 2
lib/models/network.js   createNetwork{}/ 2
lib/models/network.js   createNetwork{}/pipeline()/ 2
lib/models/network.js   createNetwork{}/pipeline()/_createIPs{}/ 2
lib/models/nic/common.js   validateSubnetContainsIP{}/ 1
lib/util/ip.js   isRFC1918{}/ 2
lib/util/ip.js   isRFC1918{}/some()/ 2
lib/util/ip.js   isRFC1918{}/some()/function{}/ 2
lib/util/subnet.js   fromNumberArray{}/ 4
lib/util/subnet.js   fromNumberArray{}/ntoa()/ 1
lib/util/subnet.js   fromNumberArray{}/Number()/ 1
lib/util/subnet.js   toNumberArray{}/ 4
lib/util/subnet.js   toNumberArray{}/toIPAddr()/ 1
lib/util/subnet.js   toNumberArray{}/Number()/ 1
lib/util/validate.js   validateSubnet{}/ 4
lib/util/validate.js   validateSubnet{}/toIPAddr()/ 1
lib/util/validate.js   validateSubnet{}/Number()/ 1

It is clearly used in the aforementioned _createIPs function. It is also used in subnet validation, IP validation, provision-range validation, network initialization, the Network constructor, network serialization, and route validation.

Let's take a closer look at _createIPs .

] ./blip index-get-subtrees-str createNetwork{}/pipeline()/_createIPs{}/ 
lib/models/network.js:

function _createIPs(_, cb) 
{
	var ipsToCreate = {};
	if (network.params.gateway) {
		if (network.fabric && !network.params.internet_nat &&
		    network.params.owner_uuids) {
			ipsToCreate[network.params.gateway.toString()] =
			    userReservedIP(network, network.params.gateway,
			        network.params.owner_uuids[0]);
		} else {
			ipsToCreate[network.params.gateway.toString()] =
			    adminReservedIP(network, network.params.gateway,
			        app.config.ufdsAdminUuid);
		}
	}
	for (var r in network.params.resolvers) {
		var num = network.params.resolvers[r];
		if (network.subnet.contains(num) && !ipsToCreate.hasOwnProperty(
		   num.toString())) {
			ipsToCreate[num.toString()] = adminReservedIP(network,
			    num, app.config.ufdsAdminUuid);
		}
	}
	if (network.family === 'ipv4') {
		var maxIP = network.subnet.broadcast();
		if (!ipsToCreate.hasOwnProperty(maxIP.toString())) {
			ipsToCreate[maxIP.toString()] = adminReservedIP(network,
			    maxIP, app.config.ufdsAdminUuid);
		}
	}
	var lowerBound = util_ip.ipAddrMinus(network.provisionMin, 1);
	var upperBound = util_ip.ipAddrPlus(network.provisionMax, 1);
	[lowerBound, upperBound].forEach(<<< function{}/ >>>);
	var batch = {
		batch : Object.keys(ipsToCreate).sort().map(<<< function{}/ >>>),
		network_uuid : network.uuid,
		network : network
	};
	log.info(batch, 'Reserving IPs for network "%s"', network.uuid);
	return mod_ip.batchCreate(app, log, batch, cb);
}

So, we clearly iterate across the entire provision range, create a batch of IPs in that range, and then use batchCreate to declare that those IPs are now reserved by the network we are creating.

We want to do something similar for subnets. Except we don't have a range ahead of time. Instead we want to walk a stream of all subnets that have been allocated, and find a gap between two subnets that we can stick our new subnet into.

We will want to do this at the beginning of the pipeline, before we store the network object via _createNetObj . The reasoning behind this is that we validate the parameters, which includes subnet validation. The subnet validator adds new members to our params object, which the Network constructor expects to be present. So, we want to make sure that the subnet is available otherwise the constructor will trip an assertion.

We would likely want to do this via lomstream which is used elsewhere in the repo. Let's find out where.

] ./blip index-prefix LOMStream up 
lib/models/network.js:

LOMStream()/function{}/validateListNetworks()/listNetworksStream{}/

] ./blip index-prefix listNetworksStream up 
lib/endpoints/search.js:

listNetworksStream()/function{}/params()/searchIPs{}/


lib/models/network.js:

listNetworksStream{}/

It's used to power the searchIPs endpoint. Let's take a look at how it's used:

] ./blip index-get-subtrees-str listNetworksStream{}/validateListNetworks()/function{}/ 
lib/models/network.js:

function (err, params) 
{
	var s,dupOpts;
	if (err) {
		return callback(err);
	}
	dupOpts = jsprim.deepCopy(opts);
	dupOpts.params = params;
	s = new lomstream.LOMStream({
		fetch : listNetworksFetch,
		limit : constants.DEFAULT_LIMIT,
		offset : true,
		fetcharg : dupOpts
	});
	return callback(null, s);
}

We can see that it fetches networks via listNetworksFetch . Let's see what that looks like.

] ./blip index-prefix listNetworksFetch 
lib/models/network.js:

listNetworksFetch{}/
listNetworksFetch{}/object()/
listNetworksFetch{}/number()/
listNetworksFetch{}/number()/
listNetworksFetch{}/object()/
listNetworksFetch{}/deepCopy()/
listNetworksFetch{}/listNetworks()/
listNetworksFetch{}/listNetworks()/function{}/
listNetworksFetch{}/listNetworks()/function{}/callback()/
listNetworksFetch{}/listNetworks()/function{}/callback()/

Clearly this is a wrapper around listNetworks which bridges it to LOMStream . Let's take a look at listNetworks .

] ./blip index-prefix listNetworks{}/ 
lib/endpoints/networks/index.js:

listNetworks{}/
listNetworks{}/list()/
listNetworks{}/list()/function{}/
listNetworks{}/list()/function{}/debug()/
listNetworks{}/list()/function{}/next()/
listNetworks{}/list()/function{}/push()/
listNetworks{}/list()/function{}/push()/serialize()/
listNetworks{}/list()/function{}/send()/
listNetworks{}/list()/function{}/next()/


lib/models/network.js:

listNetworks{}/
listNetworks{}/validateListNetworks()/
listNetworks{}/validateListNetworks()/function{}/
listNetworks{}/validateListNetworks()/function{}/callback()/
listNetworks{}/validateListNetworks()/function{}/Number()/
listNetworks{}/validateListNetworks()/function{}/Number()/
listNetworks{}/validateListNetworks()/function{}/isArray()/
listNetworks{}/validateListNetworks()/function{}/forEach()/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/push()/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/push()/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/push()/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/push()/
listNetworks{}/validateListNetworks()/function{}/forEach()/function{}/push()/
listNetworks{}/validateListNetworks()/function{}/listObjs()/

So, at the very end of the validate-call, listNetworks 's callback calls listObjs . I was expecting findObjects , which is how we get data from Moray. Let's see if listObjs wraps around findObjects .

] ./blip index-prefix listObjs 
lib/apis/moray.js:

listObjs{}/
listObjs{}/optionalNumber()/
listObjs{}/optionalNumber()/
listObjs{}/ldapFilter()/
listObjs{}/debug()/
listObjs{}/findObjects()/
listObjs{}/on()/
listObjs{}/on()/_onListErr{}/
listObjs{}/on()/_onListErr{}/callback()/
listObjs{}/on()/
listObjs{}/on()/_onListRec{}/
listObjs{}/on()/_onListRec{}/debug()/
listObjs{}/on()/_onListRec{}/keys()/
listObjs{}/on()/_onListRec{}/forEach()/
listObjs{}/on()/_onListRec{}/forEach()/function{}/
listObjs{}/on()/_onListRec{}/push()/
listObjs{}/on()/_onListRec{}/push()/model()/
listObjs{}/on()/_onListRec{}/push()/
listObjs{}/on()/
listObjs{}/on()/_endList{}/
listObjs{}/on()/_endList{}/callback()/

Indeed it does. Since we're poking at the Moray-NAPI boundary, Let's see what else calls findObjects .

] ./blip index-prefix findObjects up 
lib/apis/moray.js:

findObjects()/listObjs{}/


lib/models/ip/index.js:

findObjects()/function{}/params()/listNetworkIPs{}/


lib/models/ip/provision.js:

findObjects()/nextFreedIPsonNetwork{}/


lib/models/network-pool.js:

findObjects()/function{}/params()/listNetworkPools{}/

So, it's a bit surprising that functions with the word "list" in the name make direct calls to findObjects instead of calling listObjs . To avoid boring you (more), listObjs essentially wraps an event-emitter based interface in a callback-based interface. listObjs and the invocations of findObjects seem equivalent in functionality, otherwise.

So, just like searchIPs we will want to use a listNetworks -like function that is wrapped in a LOMStream stream. However, instead of searching for IPs, we will be listing subnets, and comparing pairs of them to detect gaps. As soon as we find a gap, we will get the first subnet in that gap, and use that as the subnet for our network.

This implies that we will have to look at more than one subnet at a time. So while we are reading the stream we will maintain a look-behind of at least one. Put differently, we maintain a sliding window for subnets, and check for the existence of a gap between any 2 consecutive subnets. If there is a gap, we extract the first subnet from that gap and use that as the subnet for the network, in the aforementioned pipeline.

You can see the changes that have been made to NAPI so far over here .

Former user commented on 2018-02-16T22:00:17.481-0500 (edited 2018-02-20T18:46:16.393-0500):

Overview

It has been a while since I looked at the changes associated with this ticket, and they have been through a few review cycles. In the interest of making life for my future self – and any future reviewers – easier and less confusing, I am going to describe the changes so far so that neither of us has to wade through sewage any more than we have to. I will update this comment as the repo changes and gets updated.

The previous comment describes where various things like validation happen in an unmodified repo, and how they relate to the task at hand. This comment will describe the actual manifestation of our previously planned changes.

A lot of the logic is in lib/model/networks.js . This is the file with the most changes. It implements the subnet allocation, within its network-creation pipeline.

We have placed various helpers that the subnet-allocation code in lib/model/networks.js will use in lib/util/autoalloc.js . It exports five routines that are either used by lib/model/networks.js or by various test-code in tests/ .

Additionally, there is a new validator in lib/util/validate.js , a few new errors in lib/util/errors.js , and a related constant in lib/util/constants.js .

Helpers Overview

Starting with the helpers in lib/util/autoalloc.js , we have 3 kinds of public facing functions. Functions that increment or decrement a subnet, functions that deal with subnet adjacency, and functions that have to do with allocation. Below is a list:

allocProvisionRange
decrementSubnet
incrementSubnet
haveGapBetweenSubnets
subnetsAdjacent

All of these functions, are use consumed by lib/model/networks.js , with the exception of networksAdjacent . That's basically an internal function that we expose to the test-suite for testing. All of the consumed functions are consumed in allocateSubnet , which is defined in the aforementioned file.

Errors Overview

This file has two new exports: a new restify error named SubnetsExaustedError , and an error sorting function named sortErrsByField . The former is used in allocateSubnet , and the latter is used in two validation functions in the same file: validateSubnetAutoalloc , and validateSubnetParamsAlloc .

Validator Overview

This file exports a single, validator that validates the subnet prefix. Internall called validateSubnetPrefix and externally known as subnetPrefix

Main Logic Overview

Now that we have touched on the auxiliary functions, we can move on to the core of the logic located in lib/model/networks.js . We will drill down into the auxiliary functions as we encounter them.

At the very highest level, we call to createNetwork . In sequence, this function validates the input params allocates a subnet if it is told to, creates an in-memory network object using that subnet, creates a corresponding network object in Moray, and finally it creates an IP-bucket and some IPs (also in moray).

Here is a more visual overview of that function:

lib/models/network.js:

function createNetwork(opts, callback) 
{
	var app = opts.app;
	var log = opts.log;
	var network;
	var params = opts.params;
	var validatedParams;
	var copts = {
		app : app,
		fabric : opts.fabric,
		log : log,
		owner_uuid : opts.owner_uuid
	};
	log.debug(params, 'createNetwork: entry');
	vasync.pipeline({
		funcs : [<<< _validateHttpParams{}/ >>>
		, <<< _allocateSubnet{}/ >>>
		, <<< _createNetObj{}/ >>>
		, <<< _createNet{}/ >>>
		, <<< _createIPbucket{}/ >>>
		, <<< _createIPs{}/ >>>
		]
	}, <<< function{}/ >>>);
}

The last three moray related stages don't really matter here since we only changed the first three (well 1 was split into 2, but you get the idea).

The first stage is very straight forward. It simply validates the HTTP params before it uses them to allocates a subnet and create a network object.

lib/models/network.js:

function _validateHttpParams(_, cb) 
{
	validate.params(CREATE_SCHEMA, copts, opts.params, <<< function{}/ >>>);
}

lib/models/network.js:

function (err, validParams) 
{
	if (err) {
		cb(err);
		return;
	}
	validatedParams = validParams;
	cb();
}

The second stage is where all of the allocation happens. This stage simply wraps around allocateSubnet as seen below:

lib/models/network.js:

function _allocateSubnet(_, cb) 
{
	if (!validatedParams.subnet_alloc) {
		cb();
		return;
	}
	allocateSubnet(opts, <<< function{}/ >>>);
}

When done allocating we use the result to update the params:

lib/models/network.js:

function (err, subnet) 
{
	if (err) {
		cb(err);
		return;
	}
	validatedParams.subnet_start = subnet.address();
	validatedParams.subnet_bits = subnet.prefixLength();
	var provrange = autoalloc.allocProvisionRange(subnet);
	validatedParams.provision_start_ip = provrange[0];
	validatedParams.provision_end_ip = provrange[1];
	cb();
}

Let's drill down into allocateSubnet

lib/models/network.js:

function allocateSubnet(opts, callback) 
{
	var newSub = null;
	var firstSeen = null;
	var lastSeen = null;
	var plen = opts.params.subnet_prefix;
	<<< subnetWalker{}/ >>>
	subnetPairs(opts, subnetWalker, <<< function{}/ >>>);
}

This function uses subnetPairs to walk all subnets using a sliding window of two subnets per callback. So, assuming that we have subnets A through G, they will be passed to the subnetWalker function as: (A, B) (B, C) (C, D) (D, E) (E, F) (F, G). This makes it easy to do pair-wise computations – like adjacency checks – on subnets.

subnetPairs takes two callbacks. A walker that walks all subnet-pairs, and a final callback, that gets called when we walk all subnets or otherwise experience an error while doing so.

For accounting purposes we keep track of the first and last subnets that we see. We store any allocation in newSub . Let's take a look at the subnetWalker and the final callback before we delve into how subnetPairs works.

lib/models/network.js:

function subnetWalker(pair) 
{
	if (firstSeen === null) {
		firstSeen = pair[0];
	}
	lastSeen = pair[(pair.length - 1)];
	assert.ok(pair.length <= 2);
	if (pair.length === 0) {
		newSub = ipaddr.createCIDR('10.0.0.0', plen);
	} else if (pair.length === 1 || autoalloc.haveGapBetweenSubnets(pair[0],
	   pair[1])) {
		if (newSub === null) {
			newSub = autoalloc.incrementSubnet(pair[0], plen);
		}
	}
}

The walker is the core of our logic. It is what finds gaps and places subnets inside of them. In short, it (1) updates the first-seen and last-seen variables mentioned above, and (2) detects if a pair of subnets has gaps. If there is a gap between two subnets, we will try to 'increment' the first one's prefix. This would give us a subnet that fits in the gap. Note that the walker can't bail out of the walk once it find the subnet – it has to walk all subnets from start to finish. This is because there are not good or canonical ways to break out of stream in node. It is doable, but I have been given the distinct impression that it is is simply not done .

In case the concept is unclear, here is an explanation. But feel free to skip this paragraph, if you get it. Subnets are essentially ranges of addresses, which in turn are just numbers. If we wanted to designate a range of integers: [1100, 1199] we could say: 1100/2 , which would represent the notion that all but the first two digits can vary. So if we want to allocate an integer range, and we have the following pair: (1100/2, 1300/2) we would notice that there is a gap, between them (via the helper function, which I will get to soon), and we would increment the prefix of 1100/2 yielding 1200/2 .

That's the high level overview of the algorithm. All the details in the code, are just plumbing for talking to Moray, and translating the integer specific notions into subnet specific ones using the ip6addr module.

Before we drill down, let's take a look at the final callback:

lib/models/network.js:

function (err) 
{
	if (err) {
		callback(err);
		return;
	}
	if (newSub) {
		callback(null, newSub);
		return;
	}
	if (!err && !newSub) {
		newSub = autoalloc.incrementSubnet(lastSeen, plen);
		if (newSub === null) {
			newSub = autoalloc.decrementSubnet(firstSeen, plen);
		}
		if (newSub !== null) {
			callback(null, newSub);
			return;
		}
	}
	callback(new errors.SubnetsExhaustedError());
}

This callback does one of two things: it handles any errors returned, or it handles the unusual edge case where we have no gaps, but still have free space . This happens when there is conigious run of subnets: G, H, I, J but the subnets before G and/or after J are unused. In other words, we have a gap at the beginning or end of the pair-stream, but we can't detect them while walking. We keep track of the first-seen and last-seen subnets so that we increment/decrement them if we run into this edge case.

Helper Drill Down

Now we can move on to the helper functions. Let's start with gap-detection. Here are the relevant function definitions, from the top down:

lib/util/autoalloc.js:

function haveGapBetweenSubnets(s1, s2) 
{
	return (!subnetsAdjacent(s1, s2));
}

lib/util/autoalloc.js:

function subnetsAdjacent(sn1, sn2) 
{
	var prev = previousAddr(sn2.address());
	return sn1.contains(prev);
}

lib/util/autoalloc.js:

function previousAddr(addr) 
{
	if (addr.compare(IP_10_0_0_0) === 0) {
		throw new Error('address should always be decrementable');
	} else if (addr.compare(IP_172_16_0_0) === 0) {
		return IP_10_255_255_255;
	} else if (addr.compare(IP_192_168_0_0) === 0) {
		return IP_172_31_255_255;
	} else {
		return addr.offset(- 1);
	}
}

In short we rely on the subnet-specific arithmetic and range-checking methods that come with the ip6addr module. As for the increment and decrement code, it's a similar story:

lib/util/autoalloc.js:

function incrementSubnet(cidr, nlen) 
{
	assert.number(nlen, 'nlen');
	var plen = cidr.prefixLength();
	var adjustedCIDR = ipaddr.createCIDR(cidr.address(), Math.min(plen,
	    nlen));
	var naddr = incSubImpl(adjustedCIDR, nlen);
	return naddr;
}

lib/util/autoalloc.js:

function incSubImpl(addr, plen) 
{
	var new_addr = addr.last().offset(2);
	if (new_addr.compare(IP_11_0_0_0) === 0) {
		new_addr = IP_172_16_0_0;
	} else if (new_addr.compare(IP_172_32_0_0) === 0) {
		new_addr = IP_192_168_0_0;
	} else if (new_addr.compare(IP_192_169_0_0) === 0) {
		return null;
	}
	return ipaddr.createCIDR(new_addr, plen);
}

lib/util/autoalloc.js:

function decrementSubnet(cidr, nlen) 
{
	assert.number(nlen, 'nlen');
	var plen = cidr.prefixLength();
	var adjustedCIDR = ipaddr.createCIDR(cidr.address(), Math.min(plen,
	    nlen));
	var naddr = decSubImpl(adjustedCIDR, nlen);
	return naddr;
}

lib/util/autoalloc.js:

function decSubImpl(addr, plen) 
{
	var new_addr = addr.address().offset(- 1);
	if (new_addr.compare(IP_9_255_255_255) === 0) {
		return null;
	} else if (new_addr.compare(IP_172_15_255_255) === 0) {
		new_addr = IP_10_255_255_0;
	} else if (new_addr.compare(IP_192_167_255_255) === 0) {
		new_addr = IP_172_31_0_0;
	}
	return ipaddr.createCIDR(new_addr, plen);
}

Lest we forget, here is the code for allocProvisionRange which is used in the callback passed to allocateSubnet from within the top-level pipeline. It simply return the range of a subnet:

lib/util/autoalloc.js:

function allocProvisionRange(subnet) 
{
	if (typeof(subnet) === 'string') {
		subnet = ipaddr.createCIDR(subnet);
	}
	var first = subnet.first();
	var last = subnet.last();
	return[first.toString(), last.toString()];
}

And that covers the helpers.

Subnet Pair Stream Drill Down

Now for the plumbing that gets stream of subnet pairs into the aforementioned main logic:

lib/models/network.js:

function subnetPairs(opts, walker, callback) 
{
	var filter = '(vnet_id=' + opts.params.vnet_id + ')';
	var pair = [];
	<<< updatePair{}/ >>>
	var stream = listFilteredNetworksStream(opts, filter, getMarkerSubnet,
	    'subnet');
	stream.on('error', callback);
	stream.on('readable', <<< function{}/ >>>);
	stream.on('end', <<< function{}/ >>>);
}

subnetPairs creates a stream via listFilteredNetworksStream and calls the walker and final callback part of the callbacks that we pass to the EventEmitter.on methods. Below are the callback definitions for the readable and end events, respectively:

lib/models/network.js:

function () 
{
	var network;
	for (;;) {
		network = stream.read(1);
		if (network === null) {
			return;
		}
		updatePair(network.subnet);
		if (pair.length === 2) {
			walker(pair);
		}
	}
}

function () 
{
	if (pair.length < 2) {
		walker(pair);
	}
	callback();
}

Note that walker gets called whenever we have readable data, and when the stream ends – the final callback gets called only when we have an error and when the stream ends. We only update the pair – via updatePair when we have readable data.

lib/models/network.js:

function updatePair(sub) 
{
	pair.push(sub);
	while (pair.length > 2) {
		pair.shift();
	}
}

It is a very simple implementation of a sliding window, that pass to the walker.

LOMStream Drill Down

Let's take a look at the logic behind listFilteredNetworksStream :

lib/models/network.js:

function listFilteredNetworksStream(opts, baseFilter, marker, attr) 
{
	var dupOpts = jsprim.deepCopy(opts);
	var filter;
	var s = new lomstream.LOMStream({
		fetch : <<< function{}/ >>>
		,
		marker : marker,
		limit : 10,
		fetcharg : dupOpts
	});
	return s;
}

We essentially define a LOMStream specifying a fetch function, and return that. The fetch function is where the magic happens, so let's drill down there:

lib/models/network.js:

function (opts2, lobj, _datacb, cb) 
{
	var copyOpts = jsprim.deepCopy(opts2);
	copyOpts.params.limit = lobj.limit;
	filter = addSubnetMarkerToFilter(baseFilter, lobj.marker);
	listFilteredNetworks(opts2, filter, attr, <<< function{}/ >>>);
}

Clearly the fetcher fetches networks via listFilteredNetworks using a filter that gets updated on each fetch by addSubnetMarkerToFilter . Which, as you can see below, concatenates a filter-string, in order to exclude subnets we have already seen.

lib/models/network.js:

function addSubnetMarkerToFilter(filter, marker) 
{
	if (marker) {
		return'(&' + filter + '!(subnet<=' + marker + '))';
	}
	return filter;
}

Meanwhile listFilteredNetworks is just a wraper around listObjs which – as mentioned in the previous comment – calls out to moray.

lib/models/network.js:

function listFilteredNetworks(opts, filter, attr, callback) 
{
	var app = opts.app;
	var log = opts.log;
	var offset,limit;
	mod_moray.listObjs({
		defaultFilter : '(uuid=*)',
		filter : filter,
		limit : limit,
		log : log,
		offset : offset,
		bucket : BUCKET,
		model : Network,
		moray : app.moray,
		sort : {
			attribute : attr,
			order : 'ASC'
		}
	}, callback);
}

The final callback to listFilteredNetworks may also interest you, so I'll just drop it here, even though it is pretty pedestrian:

lib/models/network.js:

function (err, nets) 
{
	if (err) {
		cb(err);
		return;
	}
	cb(null, {
		done : nets.length === 0,
		results : nets
	});
	return;
}

Conclusion

That concludes the tour of the changes, hope it was helpful...

 

 

 

What are you still doing here? It's over, go away. I have things to do, and you probably have code to review or fix. Shoo.

Former user commented on 2018-04-23T19:43:08.772-0400 (edited 2018-04-23T19:43:26.148-0400):

Just a quick note on testing: When, enabled (and when disabled), the unit and integration tests for subnet allocation don't fail. They've been run on a very recent version of COAL.

Jira Bot commented on 2018-05-22T18:59:17.737-0400:

Jira Bot commented on 2018-05-23T13:34:13.569-0400: