Posts tagged with “programming”

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.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.

5 minute podman walkthrough

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