## Fast positions in left-complete, array based binary trees

A recent question I came across when working with static left complete binary search trees.

• How to quickly calculate the position of the k'th element in the sorted order?

Suppose our search tree is as follows

nodes = [ 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 ]

8
4               12
2       6       10      14
1   3   5   7   9   11  13  15


Then the position of the 3'rd element is 9, position of 7th element is 11.

Now lets modify the question a bit further.

Calculate the position of the k'th element in the sorted order, for the subtree at position p and height h

k_child(p, h, k)


So for the subtree at position 3 (the element 12), and height 2 (a tree with a single node has height 0), the 3'rd element is at position 13 ( the element 11).
For p=3, h=1, k=3, the 3'rd element is at position 7.

Generally this is done using a while loop and the fact that the left and right child positions can be calculated by 2*p, 2*p+1 and takes O(b^2), where b is the number of bits in the numbers we are working with (typically 32 bit integers)

We can do a lot better, in O(b) as shown with the following C++ code snippet

#define k_child(p, h, k)        (((p<<h)|(k>>1))/(k&(~(k-1))))


Note: The division will be optimized to bit shifts as we are dividing by a power of 2.

It's a cute little puzzle which takes a bit of time to figure out but hopefully putting this out there will help others too :D

## man.cgi with lighttpd

This post describes setting up OpenBSDs man.cgi(8) with lighttpd on Gentoo, with OpenRC.

Reasons for choosing lighttpd over nginx:

• Native CGI binary support
• Native chroot support

Both of these are going to turn out to be very important for man.cgi(8).

## Installing man.cgi

First step would be to install a working man.cgi static binary. For this, we need to install to app-text/mandoc with the cgi USE flag:

$USE="cgi" emerge --ask --verbose app-text/mandoc  This will install a static binary /var/www/cgi-bin/man.cgi. ## Installing lighttpd The default flags for lighttpd are enough to bring in CGI wrapper support. $ emerge --ask --verbose www-servers/lighttpd


## Set up /etc/lighttpd/lighttpd.conf

I am going to assume that this server is only for serving man pages and for nothing else, in which case the following /etc/lighttpd/lighttpd.conf should suffice:

# chroot to directory (defaults to no chroot)
server.chroot            = "/var/www"

server.groupname         = "lighttpd"

var.basedir              = "/"
var.logdir               = "/var/log/lighttpd"
var.statedir             = "/var/lib/lighttpd"

server.errorlog          = var.logdir + "/error.log"
accesslog.filename       = var.logdir + "/access.log"

server.document-root     = "/"
server.pid-file          = "/var/run/lighttpd.pid"

# NOTE: the order of modules is important.
server.modules = (
"mod_access",
"mod_cgi",
"mod_accesslog"
)

server.indexfiles        = ("index.php", "index.html",
"index.htm", "default.htm")

server.use-ipv6          = "enable"

# (extensions that are usually handled by mod_cgi, mod_fastcgi, etc).
static-file.exclude-extensions = (".php", ".pl", ".cgi", ".fcgi")

$HTTP["url"] =~ "^/cgi-bin/" { cgi.assign = ( ".cgi" => "/cgi-bin/man.cgi" ) } include "mime-types.conf"  Don't start the server yet, it will fail ## Set up the /var/www chroot From the above configuration, it is clear that we need some extra directories in /var/www and with proper permissions. I am going to be a bit lax about permissions, they can be hardened if need be. $ mkdir -p /var/www/var/{{lib,log}/lighttpd,run,tmp} /var/www/man/system /var/www/dev
$chown -R lighttpd:lighttpd /var/www/var$ chmod 777 /var/www/var/{run,tmp}


## Set up the /etc/init.d/lighttpd service

Lighttpd currently needs a /dev/null to be present inside the chroot at /var/www which is not there by default.
We will modify the lighttpd init.d file to mount a devtmpfs on /var/www/dev at each start.
You can of course do it a different way; make it into a separate init, modify existing devtmpfs mounts, etc. This is good enough for local servers.

#!/sbin/openrc-run

LIGHTTPD_PID="$(grep pid${LIGHTTPD_CONF} | cut -d '=' -f 2 | tr -d \\\" | tr -d [:space:])"

depend() {
need net
use mysql logger spawn-fcgi ldap slapd netmount dns
after famd
after sshd
}

checkconfig() {
if [ ! -f "${LIGHTTPD_CONF}" ] ; then ewarn "${LIGHTTPD_CONF} does not exist."
return 1
fi

if [ -z "${LIGHTTPD_PID}" ] ; then eerror "server.pid-file variable in${LIGHTTPD_CONF}"
eerror "is not set. Please set this variable properly"
eerror "and try again"
return 1
fi
/usr/sbin/lighttpd -t -f ${LIGHTTPD_CONF} } start() { checkconfig || return 1 # Glean lighttpd's credentials from the configuration file # Fixes bug 454366 LIGHTTPD_USER="$(awk '/^server.username/{s=$3};{sub("\"","",s)};END{print s}'${LIGHTTPD_CONF})"
LIGHTTPD_GROUP="$(awk '/^server.groupname/{s=$3};{sub("\"","",s)};END{print s}' ${LIGHTTPD_CONF})" checkpath -d -q -m 0750 -o "${LIGHTTPD_USER}":"${LIGHTTPD_GROUP}" /run/lighttpd/ mount -t devtmpfs none /var/www/dev ebegin "Starting lighttpd" start-stop-daemon --start --exec /usr/sbin/lighttpd \ --pidfile "${LIGHTTPD_PID}" -- -f "${LIGHTTPD_CONF}" eend$?
}

stop() {
local rv=0
ebegin "Stopping lighttpd"
start-stop-daemon --stop --pidfile "${LIGHTTPD_PID}" umount -R /var/www/dev } reload() { if ! service_started "${SVCNAME}" ; then
eerror "${SVCNAME} isn't running" return 1 fi checkconfig || return 1 ebegin "Re-opening lighttpd log files" start-stop-daemon --pidfile "${LIGHTTPD_PID}" \
--signal HUP
eend $? } graceful() { if ! service_started "${SVCNAME}" ; then
eerror "${SVCNAME} isn't running" return 1 fi checkconfig || return 1 ebegin "Gracefully stopping lighttpd" start-stop-daemon --quiet --pidfile "${LIGHTTPD_PID}" \
--signal INT
if eend $? ; then rm -f "${LIGHTTPD_PID}"
start
fi
}


Enable and start lighttpd.

$mkdir -p /var/www/dev$ rc-update add lighttpd default
$rc-service lighttpd start  ## Set up the man pages We will copy all the man pages into /var/www/man/system and be done with the whole setup. $ cp -r /usr/share/man/.  /var/www/man/system
$cd /var/www/man/system$ makewhatis -T utf8 .
$emerge -av podman  ## Setup podman The default configuration file provided (/etc/containers/registries.conf.example) does weird redirections, we don't want that. Create the config file (/etc/containers/registries.conf) from scratch: [registries.search] registries = ['docker.io', 'quay.io', 'registry.fedoraproject.org'] [registries.insecure] registries = [] #blocked (docker only) [registries.block] registries = []  Create the /etc/containers/policy.json file: $ cp /etc/containers/policy.json{example,}


Optional: login to docker hub and quay.io:

$podman login docker.io Username: Password:$ podman login quay.io


### Extra - rootless mode

To enable rootless mode, the tun kernel module must be loaded.
If the tun module is built in to the kernel, then no further steps are necessary.

Look at the Gentoo wiki article on kernel modules for an in-depth explanation.

tun


## Basic terminology

### Pods

For practical purposes, pods are going to be a collection of containers.
All containers inside a pod share a network namespace.

If running a pod in macvlan mode, this means all containers in the pod get the same IP address.

### Containers

containers are lightweight emulation environments, designed for running programs in isolation from each other.
For our purposes, we will be running small services for our homeserver, with the specific example in this document for the jackett torrent tracker.

## Extra - creating a podman network - macvlan

The default config provided only allows for publishing specific ports for containers/pods and provides the default network config podman. We will create a new network which will allow pods/containers to get real IPs on the LAN.

Create the /etc/cni/net.d/88-macvlan.conflist config file:

{
"cniVersion": "0.4.0",
"name": "macvlan",
"plugins": [
{
"type": "macvlan",
"master": "br0",
"isGateway": true,
"ipam": {
"type": "dhcp"
}
},
{
"type": "portmap",
"capabilities": {
"portMappings": true
}
},
{
"type": "firewall"
},
{
"type": "tuning"
}
]
}


Note: br0 can be substituted for any preconfigured bridge on the host, or can even be an ethernet interface such as enp5s0f0, without losing connectivity for the host machine.

### Test the network config

To check that the configuration is sane:

$rc-service cni-dhcp start  ### Dangers of macvlan Exposing a pod can also expose unwanted and unsafe ports to the network, such as mistakenly exposing a redis port, if redis is employed in a container. Be careful in choosing the macvlan networking option for a pod/container. ## Running a container There are two ways of running a podman container • free floating containers - not inside a pod • containers inside a pod Here, we will only do containers inside a pod. ## Create a pod Create a very simple, empty pod, with the macvlan network. $ podman pod create --name homeserver --network macvlan


### Testing the pod

Add an alpine container to the homeserver pod:

$podman run --detach --tty --pod homeserver --name homeserver_alpine docker.io/library/alpine:latest top  man podman-run gives a more thorough review of all the command options: • --detach: Detached mode: run the container in the background and print the new container ID. The default is false. • --tty: Allocate a pseudo-TTY. The default is false. This creates an alpine linux container inside the homeserver pod and runs the command top in it. To view the IP address of this pod: $ podman exec homeserver_alpine ifconfig
UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
RX packets:14 errors:0 dropped:0 overruns:0 frame:0
TX packets:13 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:0
RX bytes:1976 (1.9 KiB)  TX bytes:1552 (1.5 KiB)

UP LOOPBACK RUNNING  MTU:65536  Metric:1
RX packets:0 errors:0 dropped:0 overruns:0 frame:0
TX packets:0 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:1000
RX bytes:0 (0.0 B)  TX bytes:0 (0.0 B)


## Creating a container inside a pod

We can now run the jackett container in this pod with:

\$ podman run --detach --tty --pod homeserver --name=homeserver_jackett ghcr.io/linuxserver/jackett


### Test the container

From the above configuration, try to access the jackett webui - http://192.168.2.122:9117

## Voila

We are done!
This setup gets rid of pesky port forwarding options and firewall configurations , though at the cost of a potential risk.
Be wise before choosing this configuration.

## References

Official documentation - https://docs.podman.io/en/latest/index.html