## December 2020

• #### man.cgi with...

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.

Permanent link to “man.cgi with lighttpd”

## October 2020

• #### Fast positions in...

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

Permanent link to “Fast positions in left-complete, array based binary trees”