dental floss for your pc

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

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.username          = "lighttpd"
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.follow-symlink    = "enable"

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
# Copyright 1999-2016 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2

extra_started_commands="reload graceful"

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 .
$ echo "system" > /var/www/man/manpath.conf

AND WE ARE DONE

Visit http://localhost/cgi-bin/man.cgi/ to check out them sexy man pages.

This is yet another one of the guides on how to do backups for a server, this time with restic and OpenBSD. This sets up a daily backup and mails the changes to root.

Install restic

This is the simplest part:

$ pkg_add restic

Setup a restic repository

From the official instructions, the example here sets up an sftp repository over ssh. For this to work, root must have access to the backup server using its ssh key.

$ cat /root/.ssh/config
Host truenas
	HostName 192.168.4.2
	User restic
	IdentityFile /root/.ssh/id_ed25519

$ restic --repo sftp:truenas:/mnt/Media/backups/fwall init

Store the password that was used in plain text in /root/.ssh/restic:

$ ls -lh /root/.ssh/restic
-rw-------  1 root  wheel    18B Dec 24 20:32 /root/.ssh/restic

$ cat /root/.ssh/restic
SomeReallyCoolResticPassword

NOTE: Make sure that the ssh user, restic, has full access to the backup folder.

Setup /etc/daily.local

Create a new file /etc/daily.local.restic with the contents:

# backup restic
R_FILE="/root/.ssh/restic"
R_REPO="sftp:truenas:/mnt/Media/backups/fwall"
env RESTIC_PASSWORD_FILE="${R_FILE}" \
HOME="/root" \
/usr/local/bin/restic --repo ${R_REPO} \
	--verbose backup \
	--exclude-if-present=no_restic \
	--exclude-file=/etc/restic.exclude \
	--files-from=/etc/restic.include \
	--tag="$(date +%c)"

# list changes
PREV=$(env RESTIC_PASSWORD_FILE="${R_FILE}" HOME="/root" \
	/usr/local/bin/restic --repo ${R_REPO} \
	snapshots --compact | tail -4 | head -1 | awk '{print $1}')
LAST=$(env RESTIC_PASSWORD_FILE="${R_FILE}" HOME="/root" \
	/usr/local/bin/restic --repo ${R_REPO} \
	snapshots --compact | tail -3 | head -1 | awk '{print $1}')

RDIFF_FILE="$(mktemp)"
env RESTIC_PASSWORD_FILE="${R_FILE}" HOME="/root" \
	/usr/local/bin/restic --repo ${R_REPO} \
	diff ${PREV} ${LAST} > ${RDIFF_FILE}

NLINES=$(wc -l "${RDIFF_FILE}" | awk '{print $1}')
if [ ${NLINES} -gt 108 ] ; then
	head -n 100 "${RDIFF_FILE}"
	printf "======= SNIP ======\n"
	tail -n 8 "${RDIFF_FILE}"
else
	cat "${RDIFF_FILE}"
fi
rm -f "${RDIFF_FILE}"
unset R_REPO R_FILE RDIFF_FILE NLINES

And in the /etc/daily.local, add a line which sources /etc/daily.local.restic:

...
{other personal scripts}
...
. /etc/daily.local.restic

This sets up the daily script, which backs up the whole system. We still need to create the config files /etc/restic.include and /etc/restic.exclude.

/etc/restic.include:

/etc
/root
/home
/usr
/bin
/sbin
/var

/etc/restic.exclude:

/var/run
/var/spool
/var/tmp

Any folder which contains a file named no_restic is also excluded. For example, if a user has multiple git repositories in /home/aisha/GIT/ and they wish to avoid backups of this folder, create a file /home/aisha/GIT/no_restic, an empty file is fine, it can also contain the reason for excluding this folder.

$ locate no_restic
/home/aisha/GIT/no_restic

$ cat /home/aisha/GIT/no_restic
no need to do backups of online version controlled folders

Test backup

To test it out, first do a full back of the system:

$ env -i R_FILE="/root/.ssh/restic" \
    R_REPO="sftp:truenas:/mnt/Media/backups/fwall" \
    RESTIC_PASSWORD_FILE="${R_FILE}" \
    HOME="/root" \
    /usr/local/bin/restic --repo ${R_REPO} \
    --verbose backup \
    --exclude-if-present=no_restic \
    --exclude-file=/etc/restic.exclude \
    --files-from=/etc/restic.include \
    --tag="$(date +%c)"

Now do a test run of /etc/dailly.local.restic with:

$ sh /etc/daily.local.restic
open repository
repository f719d564 opened successfully, password is correct
lock repository
load index files
using parent snapshot 05b3f0dd
start scan on [/etc /root /home /usr /bin /sbin /var]
start backup on [/etc /root /home /usr /bin /sbin /var]
scan finished in 2.230s: 35818 files, 2.111 GiB

Files:           0 new,    10 changed, 35808 unmodified
Dirs:            0 new,    12 changed,  1859 unmodified
Data Blobs:      8 new
Tree Blobs:     11 new
Added to the repo: 817.516 KiB

processed 35818 files, 2.111 GiB in 0:05
snapshot 11d4745c saved
comparing snapshot 05b3f0dd to 11d4745c:

M    /root/.local/share/nvim/shada/main.shada
M    /var/cron/log
M    /var/cron/log.0.gz
M    /var/cron/log.1.gz
M    /var/cron/log.2.gz
M    /var/log/daemon
M    /var/log/dhcpd
M    /var/log/messages
M    /var/log/pflog
M    /var/log/rad

Files:           0 new,     0 removed,    10 changed
Dirs:            0 new,     0 removed
Others:          0 new,     0 removed
Data Blobs:      8 new,     8 removed
Tree Blobs:     10 new,    10 removed
  Added:   815.139 KiB
  Removed: 821.155 KiB

Congratulations

This sets up proper daily backups for the server, with blazing speed.

Machine - Gentoo amd64 + OpenRC.

Installing podman

We want to use app-emulation/crun instead of app-emulation/runc - Bug 723080.

$ emerge -av1 app-emulation/crun
$ 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
Username:
Password:

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.

For loading the tun module, create the file /etc/modules-load.d/networking.conf, with the single line:

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:

$ podman network ls
NAME           VERSION  PLUGINS
podman         0.4.0    bridge,portmap,firewall,tuning
macvlan        0.4.0    macvlan,portmap,firewall,tuning

Virtual DHCP server for containers

Most containers are not going to have a dhcp client present and thus will not get IP addresses from the dhcp server.

Luckily, net-misc/cni-plugins provides a virtual dhcp server/client which assigns the IP addresses to them. It is pulled in automatically as a dependency.

Start the dhcp server with:

$ rc-update add cni-dhcp default
$ 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
eth0      Link encap:Ethernet  HWaddr 82:82:CF:4F:6F:DD  
          inet addr:192.168.2.122  Bcast:192.168.2.255  Mask:255.255.255.0
          inet6 addr: fe80::8082:cfff:fe4f:6fdd/64 Scope:Link
          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)

lo        Link encap:Local Loopback  
          inet addr:127.0.0.1  Mask:255.0.0.0
          inet6 addr: ::1/128 Scope:Host
          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