DEV Community: Junxiao Shi

Today I Learned: openat()

Junxiao Shi — Sat, 28 Aug 2021 17:53:27 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/openat/

fopen and open

In C programming language, the <stdio.h> header supplies functions for file input and output.
To open a file, we usually use the fopen function.
It is defined by the C language standard and works in every operating system.

Working at a lower level, there's also the open function.
It is a system call provided by the Linux kernel and exposed through glibc.

Both fopen and open have an input parameter: the file pathname, as a NUL-terminated string.
These two functions are declared like this:

FILE* fopen(const char* filename, const char* mode);

int open(const char* pathname, int flags);

If the file we want to access is in the current working directory, or we have the full pathname of the file as a string, this is easy to use.
However, sometimes we want to access a file relative to another directory, and the above API isn't so easy to use.

Directory Path + Filename

One such occasion is in my NDNph library: I wanted to use a directory in the filesystem as a persistent key-value store, where object keys are used as filenames, and object value is written as file content.
The API for this key-value store looks like this:

typedef struct KV KV;

/**
 * @brief Open a key-value store at specified path
 * @param[out] kv key-value store object
 * @param dir directory pathname
 * @return whether success
 */
bool KV_Open(KV* kv, const char* dir);

/**
 * @brief Write @p value to file @p dir "/" @p key
 * @param kv key-value store object
 * @param key filename
 * @param value file content
 * @param size size of file content
 * @return whether success
 */
bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size);

Since fopen and open want the file pathname as a single string, I have to concatenate dir and key in KV_Save.
This in turn requires saving a copy of dir in KV_Open function.

typedef struct KV
{
  char* dir;
} KV;

bool KV_Open(KV* kv, const char* dir)
{
  struct stat st;
  if (stat(dir, &st) != 0 || !S_ISDIR(st.st_mode)) {
    return false;
  }
  kv->dir = strdup(dir);
  return true;
}

bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size)
{
  char pathname[PATH_MAX];
  int res = snprintf(pathname, sizeof(pathname), "%s/%s", kv->dir, key);
  if (res < 0 || res >= sizeof(pathname)) {
    return false;
  }

  int fd = open(pathname, O_WRONLY | O_CREAT, 0644);
  if (fd < 0) {
    return false;
  }

  // TODO write and close file
}

openat

This week, I came across a new function: openat.
It operates in the same way as open, except that it supports specifying a relative pathname interpreted relative to another directory, which is represented by a file descriptor.

The function signature of openat is:

int openat(int dirfd, const char* pathname, int flags);

This allows me to simplify the key-value store:

typedef struct KV
{
  int dirfd;
} KV;

bool KV_Open(KV* kv, const char* dir)
{
  kv->dirfd = open(dir, O_RDONLY | O_DIRECTORY);
  return kv->dirfd >= 0;
}

bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size)
{
  int fd = openat(kv->dirfd, key, O_WRONLY | O_CREAT, 0644);
  if (fd < 0) {
    return false;
  }

  // TODO write and close file
}

KV_Open opens the directory as a file descriptor with the open function.
The O_DIRECTORY flag ensures we are opening a directory instead of a regular file.
It's no longer necessary to save a copy of the directory path.

KV_Save calls openat with the directory file descriptor and the filename key.
It's no longer necessary to perform string concatenation.
The code is 5 lines shorter than the open-based solution.

Conclusion and Code Download

This article introduces Linux openat syscall that I recently discovered.
The openat function enables resolving a filename or relative path, relative to another directory that is not the current working directory.
It can do so without requiring manual string concatenation.

Code samples (whole program including load/save/delete functions):

open.c: key-value store implemented with open
openat.c: key-value store implemented with openat
view on GitHub Gist

Caution: this proof-of-concept code assumes that key is a valid filename.
It cannot safely handle untrusted and potentially malicious input.

Deep Atlantic Storage: Streaming Bits

Junxiao Shi — Sun, 11 Jul 2021 19:42:27 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-stream-bits/

I'm bored on 4th of July holiday, so I made a wacky webpage: Deep Atlantic Storage.
It is described as a free file storage service, where you can upload any file to be stored deep in the Atlantic Ocean, with no size limit and content restriction whatsoever.
How does it work, and how can I afford to provide it?

This article is the third of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The first part revealed that the uploaded file is sorted which drastically reduces its storage demand, and introduced the bit sorting algorithm.
The second part covered how to process the upload in the browser using Web Workers.
Now I'd continue from there, and explain where I store the files and how I offer downloads with reasonable costs.

Storage in the URL

Deep Atlantic Storage sorts the bits in every uploaded file.
After sorting, each file can be represented by two numbers: the number of 0 bits, the number of 1 bits.
Given these two numbers, the sorted file can be reconstructed.

I could make a database or use one of those fancy NoSQL thingy to store those numbers that represent the files, but I prefer my websites stateless so that I don't need to take backups.
Therefore, I decided to encode those numbers in the URI.

Each URI created by the Deep Atlantic Storage looks like this:

https://summer-host-storage.yoursunny.dev/6705fb/18fa05/%E2%98%80%EF%B8%8F.bin
                                          ^        ^          ^
                                          zeros    ones       filename
                                          (in hexadecimal)    (URI encoded)

Whenever someone requests this URI, the server program can extract the number of 0 bits and 1 bits from the URI, and reconstruct the sorted file accordingly.
By having all the information in the URI itself, I can run a storage service without maintaining any server-side storage.

Bit Counts » Byte Array

Given the number of 0 bits and 1 bits in a file, how to generate a file with those bits?
The naive way is:

Generate a string of "0" and "1" repeated for requested length.
Parse the string into an array of bytes.
Write those bytes to a file.

The code looks like this:

def makeFileFromBitCounts(filename: str, cnt0: int, cnt1: int) -> None:
    bitString = '0' * cnt0 + '1' * cnt1
    byteCount = (cnt0 + cnt1) // 8
    arrayOfBytes = int(bitString, base=2).to_bytes(byteCount, byteorder='big')
    with open(filename, mode='wb') as f:
        f.write(arrayOfBytes)

However, this approach is vastly inefficient in memory usage:

The array of bytes has the length of the entire file, and it is allocated in memory.
Even worse, the bit string has 8x the file size, demanding even more memory.

Bit Counts » Stream

Instead of reconstructing the file as a byte array in the memory, I can write the bits to an output stream (which could be a file or a network socket) as I generate them.
However, there's one little problem: in most programming languages, the stream I/O functions are byte-oriented, not bit-oriented.
In other words, I can only write bytes, not bits, to the stream.

Looking at the structure of a sorted file in bytes, it has three parts:

A consecutive run of 0x00 bytes.
Possibly, one byte that is neither 0x00 nor 0xFF.
A consecutive run of 0xFF bytes.

In order to write the file to a stream using byte-oriented API, I need to calculate three things:

The number of 0x00 bytes.
Whether the middle byte exists, and its value.
The number of 0xFF bytes.

Since each byte has 8 bits, suppose there are cnt0 zero bits and cnt1 one bits:

The number of 0x00 bytes should be cnt0 ÷ 8, rounded down.
The number of 0xFF bytes should be cnt1 ÷ 8, rounded down.
If the whole bytes did not cover all the bits, there would be a middle byte.
- This byte should contain cnt0 mod 8 zeros and cnt1 mod 8 ones.
- Since cnt0 + cnt1 is divisible by 8, (cnt0 mod 8) + (cnt1 mod 8) is expected to equal 8.
- Bit numbering within a byte can go either direction, but I picked "Most Significant Bit first" order.

The following code does the calculations and writes the bits to an output stream (try on Coliru):

void
streamFileFromBitCounts(std::ostream& os, size_t cnt0, size_t cnt1)
{
  assert((cnt0 + cnt1) % 8 == 0);

  size_t bytes0 = cnt0 / 8;
  size_t bytes1 = cnt1 / 8;

  std::optional<uint8_t> middleByte;
  size_t middle0 = cnt0 % 8;
  size_t middle1 = cnt1 % 8;
  if (middle0 + middle1 > 0) {
    assert(middle0 + middle1 == 8);
    middleByte = 0xFF >> middle0;
  }

  for (size_t i = 0; i < bytes0; ++i) {
    os.put(static_cast<uint8_t>(0x00));
  }
  if (middleByte.has_value()) {
    os.put(middleByte.value());
  }
  for (size_t i = 0; i < bytes1; ++i) {
    os.put(static_cast<uint8_t>(0xFF));
  }
}

Deep Atlantic Storage runs this logic on a server rather than in the browser.
While Blob API and URL.createObjectURL() allow generating a downloadable file from JavaScript, the entire file must be allocated in memory.
Browser support for streaming from JavaScript is still at an early stage.

Stream » HTTP Server

Deep Atlantic Storage offers file downloads from an HTTP server.
The server, dubbed Deep Atlantic Storage app, is built upon the logic above, with a few improvements:

The response is piped through a gzip compressor, in order to save network egress from my server.
For long runs of 0x00 and 0xFF bytes, instead of writing one byte at a time, the program writes them in pages of 1MB each.
A small delay is added after writing each page to throttle the downloads and avoid consuming too much CPU.
If the client has disconnected, stop writing and return right away.

This is the HTTP handler implementation:

var (
  buf0 = make([]byte, 1048576)               // create 1MB page filled with 0x00 bytes
  buf1 = bytes.Repeat([]byte{0xFF}, 1048576) // create 1MB page filled with 0xFF bytes
)

func handler(w http.ResponseWriter, req *http.Request) {
  // parse URI and extract number of zeros and ones
  var cnt0, cnt1 int
  var name string
  if _, e := fmt.Sscanf(req.URL.Path, "/%x/%x/%s", &cnt0, &cnt1, &name); e != nil {
    w.WriteHeader(http.StatusNotFound)
    return
  }

  // tell browser/client that:
  // (1) the response is binary file, not text or HTML
  // (2) the response is gzip compressed
  // (3) browser should prompt for a download instead of display the file
  w.Header().Set("Content-Type", "application/octet-stream")
  w.Header().Set("Content-Encoding", "gzip")
  w.Header().Set("Content-Disposition", "attachment")

  // calculate number of 0x00 and 0xFF pages and leftover bytes, and the middle byte
  bytes0, bytes1 := cnt0/8, cnt1/8
  middle0, middle1 := cnt0%8, cnt1%8
  pages0, pages1 := bytes0/len(buf0), bytes1/len(buf1)
  bytes0 -= pages0 * len(buf0)
  bytes1 -= pages1 * len(buf1)

  z, _ := gzip.NewWriterLevel(w, 1) // make gzip compressor, fastest mode
  defer z.Close()                   // close and flush when it's done

  writePages := func(page []byte, count int) error { // subroutine to write some pages
    ctx := req.Context()
    for i := 0; i < count; i++ {
      z.Write(page) // pipe one page to the gzip compressor
      select {
      case <-ctx.Done(): // client disconnected
        return ctx.Err() // return non-nil error
      case <-time.After(time.Millisecond): // delay 1ms and continue writing
      }
    }
    return nil
  }

  if e := writePages(buf0, pages0); e != nil { // write 0x00 pages
    return // stop if client has disconnected
  }
  z.Write(buf0[:bytes0]) // write leftover 0x00 bytes
  if middle0+middle1 > 0 { // write the middle byte, if there is one
    z.Write([]byte{0xFF >> middle0})
  }
  z.Write(buf1[:bytes1]) // write leftover 0xFF bytes
  writePages(buf1, pages1) // write 0xFF pages
}

The actual server has some additional logic for verifying the HTTP request verb and Accept-Encoding: gzip header.
You can see its source code in this Gist.

HTTP Server » HTTPS Server

It's 2021 and every website is expected to have HTTPS.
Moreover, the .dev domain I'm using is designated as a "secure namespace" such that most browsers won't even connect to it over plain HTTP.
Therefore, I need to deploy Deep Atlantic Storage app over HTTPS.

I turned to my favorite TLS termination solution, Caddy server, for this task.
The Caddyfile uses a reverse_proxy directive to the HTTP server:

https://summer-host-storage.yoursunny.dev {
  reverse_proxy http://127.0.0.1:3333 {
    flush_interval 1s
    transport http {
      compression off
    }
  }
}

Caddy by default would make request to the HTTP backend server with Accept-Encoding: gzip request header, and then decompress the response if the incoming request does not accept gzip compression.
This is undesirable for Deep Atlantic Storage because my server can possibly send large responses, consuming too much egress bandwidth.
Therefore, I explicitly disabled HTTP transport compression, so that the incoming request is served only if the client accepts gzip compression, and the outgoing response is always compressed.

Conclusion

This article is the final installment of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
Given the bit counts generated by Web Workers, I built and deployed a server that reconstructs the file as gzip'ed HTTP response.

While Deep Atlantic Storage started as a joke, it is a nice exercise to learn the algorithms and APIs around bits, bytes, and blobs.
I enjoyed building the app, and I hope you learned something from these articles.

Deep Atlantic Storage: Reading File Upload in Web Workers

Junxiao Shi — Sun, 11 Jul 2021 19:39:30 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-file-worker/

This article is the second of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The previous part introduced the algorithm I use to sort all the bits in a Uint8Array.
Now I'd continue from there, and explain how the webpage accepts and processes file uploads.

File Upload

File upload has always been a part of HTML standard as long as I remembered:

<form action="upload.php" method="POST" enctype="multipart/form-data">
  <input type="file" name="file">
  <input type="submit" value="upload">
</form>

This would create a Browse button that allows the user to select a local file.
When the form is submitted, the file name and content are sent to the server, and a server-side script can process the upload.

It's straightforward, but not ideal for Deep Atlantic Storage.
As explained in the last article, regardless of how large a file is, the result of sorting all the bits could be represented by just two numbers: how many 0 bits and 1 bits are in the file.
It is unnecessary to send the whole file to the server; instead, counting in the browser would be a lot faster.

File and Blob

Fast forward to 2021, JavaScript can do everything.

In JavaScript, given the DOM object corresponding to the <input type="file"> element, I can access the (first) selected file via .files[0] property.
Using files from web applications has further explanation of these APIs.

.files[0] returns a File object, which is a subclass of Blob.
Then, Blob.prototype.arrayBuffer() function asynchronously reads the entire file into an ArrayBuffer, providing access to its content.

<form id="demo_form">
<input id="demo_upload" type="file" required>
<input type="submit">
</form>
<script>
document.querySelector("#demo_form").addEventListener("submit", async (evt) => {
  evt.preventDefault();
  const file = document.querySelector("#demo_upload").files[0];
  console.log(`file size ${file.size} bytes`);
  const payload = new Uint8Array(await file.arrayBuffer());
  const [cnt0, cnt1] = countBits(payload); // from the previous article
  console.log(`file has ${cnt0} zeros and ${cnt1} ones`);
});
</script>

This code adds an event listener to the <form>.
When the form is submitted, the callback function reads the file into an ArrayBuffer and passes it as a Uint8Array to the bit counting function (countBits from the previous article).

ReadableStream

file.arrayBuffer() works, but there's a problem: if the user selects a huge file, the entire file has to be read into the memory all at once, causing considerable memory stress.
To solve this problem, I can use Streams API to read the file in smaller chunks, and process each chunk before reading the next.

From a Blob object (such as the file in the snippet above), I can call .stream().getReader() to create a ReadableStreamDefaultReader.
Then, I can repeatedly call reader.read(), which returns a Promise that resolves to either a chunk of data or an end-of-file (EOF) indication.

To process the file chunk by chunk and count how many 1 bits are there, my strategy is:

Call reader.read() in a loop to obtain the next chunk.
If done is true, indicating EOF has been reached, break the loop.
Add the number of 1 bits in each byte of the chunk into the overall counter.
Finally, calculate how many 0 bits are there from the file size, accessible via blob.size property.

async function countBitsBlob(blob: Blob): Promise<[cnt0: number, cnt1: number]> {
  const reader = (blob.stream() as ReadableStream<Uint8Array>).getReader();
  let cnt = 0;
  while (true) {
    const { done, value: chunk } = await reader.read();
    if (done) {
      break;
    }
    for (const b of chunk!) {
      cnt += ONES[b];
    }
  }
  return [8 * blob.size - cnt, cnt];
}

Web Worker

In a web application, it's best to execute complex computations on a background thread, so that the main thread can react to user interactions swiftly.
Web Workers are a simple means for web content to run scripts in background threads.
In Deep Atlantic Storage, I delegated the task of sorting or counting bits in the file to a web worker.

When the user selects a file and submits the form, the form event handler creates a Worker (if it has not done so), and calls Worker.prototype.postMessage() to pass the File object to the background thread.

let worker;
document.querySelector("#demo_form").addEventListener("submit", async (evt) => {
  evt.preventDefault();
  const file = document.querySelector("#demo_upload").files[0];
  worker ??= new Worker("worker.js");
  worker.onmessage = handleWorkerMessage; // described later
  worker.postMessage(file);
});

The worker.js runs in the background.
It receives the message (a MessageEvent enclosing a File object) in a function assigned to the global onmessage variable.
This function then calls countBitsBlob to count how many zeros and ones are in the file, then calls the global postMessage function to pass the result back to the webpage main thread.
It also catches any errors that might have been thrown, and passes those to the main thread as well.
I've included type: "result" and type: "error" in these two types of messages, so that the main thread can distinguish between them.

onmessage = async (evt) => {
  const file = evt.data;
  try {
    const result = await countBitsBlob(file);
    postMessage({ type: "result", result });
  } catch (err) {
    postMessage({ type: "error", error: `${err}` });
  }
};

Notice that in the catch clause, the Error object is converted to a string before being passed to postMessage.
This is necessary because only a handful of types can pass through postMessage, but Error is not one of them.

Back in the main thread, the handleWorkerMessage function, which was assigned to worker.onmessage property, receives messages from the worker thread.

function handleWorkerMessage(evt) {
  const response = evt.data;
  switch (response.type) {
    case "result": {
      const [cnt0, cnt1] = response.result;
      console.log(`file has ${cnt0} zeros and ${cnt1} ones`);
      break;
    }
    case "error": {
      console.error("worker error", response.error);
      break;
    }
  }
}

Combined with some user interface magic (not described in this article, but you can look at the webpage source code), this makes up the Deep Atlantic Storage webpage.

Summary

This article is the second of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
Building upon the bit counting algorithm designed in the previous article, I turned it into a web application that reads an uploaded file chunk by chunk via Streams API, and moved the heavy lifting to a background thread via Web Workers.
The next part in this series will explain how I made a server to reconstruct the file from the bit counts.

Deep Atlantic Storage: Sorting Bits

Junxiao Shi — Sun, 11 Jul 2021 19:34:11 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-sort-bits/

I'm bored on 4th of July holiday, so I made a wacky webpage: Deep Atlantic Storage.
It is described as a free file storage service, where you can upload any file to be stored deep in the Atlantic Ocean, with no size limit and content restriction whatsoever.
Since Chia currency farming became popular in May, hard drive prices went up significantly.
How can I afford to operate an unlimited free storage service?

"Advanced Sorting Technology"

One of the benefits listed on Deep Atlantic Storage webpage is:

Advanced sorting technology keeps your data neatly ordered.

What this means is that, content in the uploaded file would be sorted before being stored.

A sorting algorithm is an algorithm that puts elements of a list in a certain order, such as numerical order or lexicographical order.
Every coder knows a few sorting algorithms, such as:

quick sort
bubble sort
merge sort
insertion sort
selection sort

Most sorting algorithms are comparison sorts that rely on a comparison function to determine the relative order between two elements.
For example, the program below (try on Compiler Explorer) sorts a list of points on a two-dimensional Euclidean plane by its distance from the origin.
It uses std::sort function from the C++ standard library, passing a custom comparison function that returns true if the first point is closer to the origin point (0,0) than the second point, or false otherwise.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

struct Point
{
  double x;
  double y;
};

int main() {
  std::vector<Point> points{
    {  1.0,  2.0 },
    {  2.0,  0.9 },
    {  0.9, -2.0 },
    {  0.0,  0.0 },
    { -1.4,  0.0 },
    { -1.4, -0.7 },
  };
  std::sort(points.begin(), points.end(), [] (const Point& a, const Point& b) {
    return std::sqrt(a.x * a.x + a.y * a.y) < std::sqrt(b.x * b.x + b.y * b.y);
  });
  for (const Point& point : points) {
    std::printf("%+0.1f, %+0.1f\n", point.x, point.y);
  }
}

The input and output of a sorting algorithm are both a list of elements.
Deep Atlantic Storage deals with files.
A file must first be turned into a list of elements before it can be sorted.

There are many ways to interpret a file as a list of elements.
If the file is a database, following the database structure, each table in the database is a list of rows that can be sorted.
If the file is plain text, the Unix sort command can read it as a list of text lines that can be sorted.

In Deep Atlantic Storage, I decided to use the most basic unit of information: bit.
When you upload a file to my unlimited storage service, the bits contained in the file are sorted in ascending order.
For example, suppose the file has the text:

@yoursunny

In binary form it is:

@        y        o        u        r        s        n        n        n        y
01000000 01111001 01101111 01110101 01110010 01110011 01110101 01101110 01101110 01111001

If I sort all the bits, it becomes:

00000000 00000000 00000000 00000000 00111111 11111111 11111111 11111111 11111111 11111111

Sorting Bits » Counting Bits

Naively, I can collect every bit in the input file into a list of bits, and sort them using a "normal" sort algorithm (try on RunKit):

const input = Buffer.from("@yoursunny");
const bits = [];
for (const b of input) {
  for (let s = 0; s < 8; ++s) {
    bits.push((b >> s) & 0x01);
  }
}
let compares = 0;
bits.sort((a, b) => {
  ++compares;
  return a - b;
});
console.log(
  `${bits.length} elements`,
  `${compares} compares`,
  JSON.stringify(bits),
);

Array.prototype.sort() is a comparison sort algorithm.
Theoretically, a comparison sort algorithm cannot perform better than O(n log n) comparisons, where n is the number of elements in the input list.
For my 80-bit input, Node.js v16.3.0 invoked the comparison function 322 times.
If the input was longer, considerably more comparisons would be needed.

Since there are only two possible values, 0 and 1, for each bit, there is a better algorithm: counting sort.
Counting sort is an integer sorting algorithm suitable for a list of small non-negative integers.
It does not use a comparison function and hence is a non-comparison sorting algorithm.
Instead, counting sort first counts how many elements possess each distinct key value, then uses these counts to determine the positions of each key value in the output list.
Its time complexity is O(n+k), where n is the number of elements and k is the maximum integer key value in the list.

A counting sort on the same input can be written as (try on Go Playground):

package main

import (
    "fmt"
)

func sortBits(bits []int) (sorted []int) {
    m := make(map[int]int)
    for _, bit := range bits {
        m[bit]++
    }
    for bit := 0; bit <= 1; bit++ {
        for i, n := 0, m[bit]; i < n; i++ {
            sorted = append(sorted, bit)
        }
    }
    return sorted
}

func main() {
    var bits []int
    for _, b := range []byte("@yoursunny") {
        for s := uint(0); s < 8; s++ {
            bit := (b >> s) & 0x01
            bits = append(bits, int(bit))
        }
    }

    sorted := sortBits(bits)
    fmt.Println(sorted)
}

Sorted Bits » Bit Counts

A sorting algorithm does not change the size of the list being sorted.
Suppose a 1GB file is uploaded to Deep Atlantic Storage, there are 8589934592 bits in this file before sorting, and there would be still 8589934592 bits after sorting.
Storing a sorted file takes as much disk space as storing the original unsorted file.

Looking at the sorted bits, there is an important observation:
after sorting, all the 0 bits are together, and all the 1 bits are together!

00000000 00000000 00000000 00000000 00111111 11111111 11111111 11111111 11111111 11111111
\_____________ 34 zeros _____________/\____________________ 46 ones ____________________/

Instead of storing the same bit repeatedly, I only need to remember: "there are 34 zeros followed by 46 ones".
This allows Deep Atlantic Storage to store sorted large files with considerably less disk space than the original files: any file, regardless of its size, can be represented by two numbers.

Given a list of sorted bits, I can iterate over the list and count the number of consecutive zeros and ones:

from itertools import groupby

bits = "00000000000000000000000000000000001111111111111111111111111111111111111111111111"
for bit, g in groupby(bits):
    print(bit, len(list(g)))

This is, in fact, the basic idea of run-length encoding, a lossless data compression method.

However, it's unnecessary to run a sorting algorithm followed by a compression algorithm.
Instead, I can let the counting sort algorithm return the counters for zeros and ones directly, skipping the unnecessary step of constructing a sorted list of bits.

Well, actually I don't even need to count both zeros and ones.
Since there are 8 bits in every byte, it suffices to only count the 1 bits, and I can calculate the number 0 bits to be 8 * bytes - ones.

With that, our bit ~~sorting~~ counting algorithm becomes:

function countBits(input: Uint8Array): [cnt0: number, cnt1: number] {
  let cnt = 0;
  for (const b of input) {
    for (let s = 0; s < 8; ++s) {
      if ((b >> s) % 2 === 1) {
        ++cnt;
      }
    }
  }
  return [8 * input.length - cnt, cnt];
}

Bit Counting » Byte Counting

Looking at the bit counting algorithm, the inner loop that iterates over the bits within a byte would be executed once for every byte, which is a hot spot worth optimization.
To optimize this code, I aim at eliminating the loop.

In a byte, there are 256 possible values between 0x00 and 0xFF.
The number of zeros and ones in each byte value never changes.
Therefore, it is unnecessary to loop over the bits every time.
Instead, I can build a lookup table that maps a byte value into the number of ~~zeros and~~ ones in that byte.

This code, executed during initialization, prepares the lookup table:

const ONES = [];
for (let b = 0x00; b <= 0xFF; ++b) {
  let cnt = 0;
  for (let s = 0; s < 8; ++s) {
    if ((b >> s) % 2 === 1) {
      ++cnt;
    }
  }
  ONES.push(cnt);
}

Using this lookup table, I can count bits in a file more efficiently:

function countBits(input: Uint8Array): [cnt0: number, cnt1: number] {
  let cnt = 0;
  for (const b of input) {
    cnt += ONES[b];
  }
  return [8 * input.length - cnt, cnt];
}

As measured on JSBEN.CH, the lookup table approach is 3~5x faster than the previous algorithm.

Summary

In this article, I reviewed commonly used sorting algorithms, explained why counting sort is more efficient on a list of bits where each bit is either 0 or 1, explored how to compactly store sorted bits as two numbers, and finally optimized the algorithm using a lookup table.

This article is the first of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The next part in this series will explain how the bit sorting aka byte counting algorithm is used in a web application.

Google Code Jam 2021 is Coming

Junxiao Shi — Fri, 26 Mar 2021 12:31:10 +0000

Code Jam is an annual programming competition organized by Google, with a focus on algorithms.

The Qualifications Round of Code Jam 2021 starts today, and continues for 30 hours.
You can register and participate at the Code Jam website: https://g.co/codejam

How Many Servers Do You Need for a Crucial Website?

Junxiao Shi — Fri, 19 Mar 2021 04:55:30 +0000

A crucial website ought to have:

a primary server: Ryzen CPU, NVMe storage.
a secondary standby: Xeon CPU, SSD storage.
a third replica: Atom CPU, spinning rust storage.
a fourth backup: ARMv5 CPU, VHS tape.
a system to automatically perform failover.
a cat to look over this system.
a robot to feed the cat.
an engineer to repair the robot.

These can get your data 99.99% secure.

Now add some cold storage:

punch cards kept in California.
microfilm buried in Antarctica.
vinyl record launched to Jupiter.

If all four online servers are lost, you are looking at a lengthy downtime, but your data would be 99.9999% secure by recovering from the cold storage.

To finally reach 100%, transmit your data as radio waves toward a black hole.
If California fells into the ocean, Antarctica melts, and the sun explodes taking out Jupiter, you can travel to the black hole and access your data.

According to physics, information cannot be destroyed by a black hole.
It's the ultimate storage with infinite space.
Once you enter the black hole, you won't be able to come back, but you are with your data forever.

OVH Strasbourg: Halt and Catch Fire, Data Uploaded to the Cloud

Junxiao Shi — Sat, 13 Mar 2021 01:21:15 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/OVH-halt-and-catch-fire/

2021-03-10, an OVH Cloud data center in Strasbourg, France caught on fire.
Thousands of servers have been destroyed by fire.
Thousands more are currently unavailable due to power cut, and will remain offline for several more days.

Data stored in those servers have been uploaded to the cloud via black smoke.

According to Hacker News, a Dev mistakenly invoked the Halt and Catch Fire instruction on an Uninterrupted Power Supply unit, causing this incident.

Chairman of OVH cloud advised clients to activate their disaster recovery plans, such as restoring off-site backups to a new cloud server.
Some clients are crying because they did not have backups, or they stored their backups on another machine in the same data center.
Other clients experienced no downtime because they designed their systems for datacenter scale redundancy.

Rename WiFi Interface on Ubuntu 20.04

Junxiao Shi — Fri, 05 Mar 2021 01:43:47 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/WiFi-rename/

During an experiment, I need to use three WiFi interfaces on a Raspberry Pi running Ubuntu 20.04.
In addition to Raspberry Pi's internal WiFi interface, I added two USB WiFi adapters.
Three network interfaces showed up in the system (ip link command), and they are named wlan0, wlan1, and wlan2 by default.

I often need to capture packets with tcpdump, and I often have to be type these interface names manually.
It isn't easy to remember the purpose of each network interface, so I wanted to rename the interfaces to reflect their role in my application.
However, this isn't as easy as it sounds.

🚫 Netplan

Ubuntu 20.04 configures network interfaces using Netplan, so my first thought was: I can write a Netplan configuration that matches network interfaces with their MAC addresses, and assigns the desired name to each network interface.

The config file would look like this:

network:
  version: 2
  wifis:
    uplink:
      optional: true
      match:
        macaddress: ba:fe:de:f0:b9:e4
      set-name: uplink
      access-points:
        home:
          password: rP8jKHJ64
      dhcp4: true
      dhcp6: true
      accept-ra: true

However, this method would not work:

$ sudo netplan apply
ERROR: uplink: networkd backend does not support wifi with match:, only by interface name

🚫 70-persistent-net.rules

Many online guides refer to a file /etc/udev/rules.d/70-persistent-net.rules, which is processed by udev during boot.
The file should have been created automatically by the system upon discovery of the network interfaces, and I just need to modify the interface names to the desired names.

However, this file does not exist in Ubuntu 20.04, so it's another dead end.

✔️ systemd.link

After carefully reading Debian's NetworkInterfaceNames guide, I found the correct way: systemd.link.

To rename WiFi interfaces, I can create a systemd configuration file for each network interface:

echo '[Match]
MACAddress=ba:fe:de:f0:b9:e4
[Link]
Name=uplink' | sudo tee /etc/systemd/network/10-uplink.link

After rebooting, the network interface is renamed to what I wanted.

What would you need 64GB of RAM for?

Junxiao Shi — Sat, 27 Feb 2021 06:09:19 +0000

This post is originally published on Quora, with code links at the end

I used 58GB of RAM once. NodeJS refuses to use more memory and I had to rewrite the program in C++.

It's in a research project. I captured a packet trace from Network File System (NFS) server, and I want to reconstruct the complete pathnames accessed in each command. The way NFS works is that, every command only carries a component of the name (like a directory name or a filename within a directory), along with a handle that represents the directory in which the file resides. To get the complete pathname, I need a lookup table of all known handles and their corresponding pathnames. Then, for each new command that has a handle and one more name component, I can query this lookup table to find out the pathname of that handle, and append the new component to get the complete pathname. Finally, I'd insert the new pathname along with the new handle into the table.

I have 24 hours of packet trace with millions of these handles. It shouldn't take so much memory, but I somehow decided to write the program in NodeJS. NodeJS struggled to allocate more and more memory as it reads the input, until it reaches 58GB after several hours. The machine has 96GB but NodeJS won't use more memory. I can tell that it's no longer making progress, because records in /proc/*/fdinfo indicates that the cursor in input file isn't moving anymore.

I spent four hours rewriting this part of the program in C++. More specifically, I hosted the lookup table in a C++ program, and had the NodeJS program communicate with C++ process via Unix socket. The program completed in 15 minutes with no more than 1GB of memory.

Conclusion: if you need 64GB of memory just for data structures, you probably need a better programming language.

source code links

https://github.com/yoursunny/nfsdump

pathtree/fullpath.js is the Node.js edition, for Node.js v0.6 on Ubuntu 12.04.
pathtree/fullpath.cc is the C++ edition implementing same functionality.

highlighted Quora comments

Michael Johnson-Moore
Conclusion 2: If you need something to be fast, don't use an interpreted language.

Alex Bujorianu
Many more developers should heed this lesson! ... I really don’t understand why a cloud desktop client, a text editor (!) etc. need 100MB of memory per instance.

Ubeyde Mavus
Or you need to know your way around C++ better than your way around NodeJS.

Hacktoberfest 2020 shirt arrived

Junxiao Shi — Sat, 20 Feb 2021 03:49:05 +0000

I managed to finish the challenge despite that the rules changed 3 times during the month. Most of my contributions went to DefinitelyTyped, a collection of TypeScript definitions that make my own life easier.

I picked the dark-colored shirt, so that it wouldn't get ruined if I decide to roll around in the mud. Yes I still do that, because it relieves stress.

GPU Accelerated Contour Detection on PiCamera

Junxiao Shi — Fri, 12 Feb 2021 03:20:53 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2018/contour-PiCamera/

Earlier this month, I spent a week building OpenCV 3.2.0, with the intention to reproduce the contour detection demo I witnessed at MoCoMakers meetup.
I successfully made contour detection working on PiCamera through MJPEG streaming.
P.S. Can you tell the Hack Arizona 2016 shirt?

How MocoMakers's Demo Works

def makeContour(image):
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    gray = cv2.GaussianBlur(gray, (3, 3), 0)
    edged = auto_canny(gray)

def auto_canny(image, sigma=0.33):
    v = np.median(image)
    lower = int(max(0, (1.0 - sigma) * v))
    upper = int(min(255, (1.0 + sigma) * v))
    edged = cv2.Canny(image, lower, upper)
    return edged

Their code works with a MJPEG stream from an Android phone.
It extracts a JPEG frame from the video stream, processes the image through makeContour function, and displays the result.
The makeContour function converts the RGB image to grayscale, blurs the grayscale image, and runs the Canny Edge Detection algorithm.

A Naive Translation

I want to have contour effect on my NoIR Camera Module, instead of an MJPEG stream from another device.
PiCamera is the official Python library to work with Raspberry Pi cameras, and it can capture still images and videos in various formats.
There is even an example of capturing a picture to an OpenCV object.

It was straightforward to stitch the code together.
This code initializes the camera, captures image frames, and processes them with the same logic as makeContour and auto_canny.
Since my Raspberry Pi Zero W isn't connected to a monitor, instead of displaying locally, I'm streaming the output as MJPEG over HTTP to another computer.

def handleContourMjpeg(self):
    import cv2
    import numpy as np
    width, height, blur, sigma = 640, 480, 2, 0.33
    self.mjpegBegin()
    with PiCamera() as camera:
        camera.resolution = (width, height)
        bgr = np.empty((int(width * height * 3),), dtype=np.uint8)
        for x in camera.capture_continuous(bgr, format='bgr'):
            image = bgr.reshape((height, width, 3))
            image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
            image = cv2.GaussianBlur(image, (3, 3), 0)
            v = np.median(image)
            lower = int(max(0, (1.0 - sigma) * v))
            upper = int(min(255, (1.0 + sigma) * v))
            image = cv2.Canny(image, lower, upper)
            self.wfile.write(cv2.imencode('.jpg', image)[1])
            self.mjpegEndFrame()

I did see the cool contour effect of my muscular body, but the frame rate was low: I got only 1.6 Frames Per Second (FPS).
1.6 FPS is not a satisfying experience, so I started optimizing the code.

Optimizing the Code: Video Port

camera.capture_continuous by default captures still images using the "image port" of the Pi camera.
For rapid capturing, I added use_video_port=True argument to this function invocation.
It asks the camera to capture a still image via the "video port", which should enable higher FPS at the expense of lower picture quality.

The performance improved to 2.6 FPS after this change.

Optimizing the Code: YUV

The first step of makeContour is converting the "bgr"-format image to grayscale.
"bgr" stands for "blue-green-red", which is one of the output formats supported by PiCamera.
Can I eliminate this step, and have PiCamera provide a grayscale image directly?

I looked through the list of supported formats, but did not find a grayscale format.
However, there is a "yuv" format, where Y stands for "luminance" or "brightness".
On the other hand, a grayscale image can be the result of measuring the intensity of light at each pixel.
Bingo!
I just need to extract the "Y" component of a YUV image, and get a grayscale image.

Where's the "Y" component?
PiCamera docs give a detailed description: for a 640x480 image, first 640x480 bytes of the array would be "Y", followed by 640x480/4 bytes of "U" and 640x480/4 bytes of "V".
Therefore, I can extract "Y" component into image variable like this:

yuv = np.empty((int(width * height * 1.5),), dtype=np.uint8)
for x in camera.capture_continuous(yuv, format='yuv', use_video_port=True):
    image = yuv[:width*height].reshape((height, width))

This change brought the most significant performance improvement: the contour camera is running at 4.7 FPS.

Optimizing the Code: Blurring in GPU

The second step of makeContour is a Gaussian blur filter.
Luckily, PiCamera gives a way to do this in the GPU:

camera.video_denoise = False
camera.image_effect = 'blur'
camera.image_effect_params = (2,)

Although the GPU's blurring effect is not exactly same as cv2.GaussianBlur, the contour still looks awesome.
The performance reached 4.9 FPS (for the same scene as other tests that is more complex than the screenshot at the beginning of this article).

The Complete Code

#!/usr/bin/python3
import time
from http.server import HTTPServer, BaseHTTPRequestHandler
from picamera import PiCamera


class MjpegMixin:
    """
    Add MJPEG features to a subclass of BaseHTTPRequestHandler.
    """

    mjpegBound = 'eb4154aac1c9ee636b8a6f5622176d1fbc08d382ee161bbd42e8483808c684b6'
    frameBegin = 'Content-Type: image/jpeg\n\n'.encode('ascii')
    frameBound = ('\n--' + mjpegBound + '\n').encode('ascii') + frameBegin

    def mjpegBegin(self):
        self.send_response(200)
        self.send_header('Content-Type',
                         'multipart/x-mixed-replace;boundary=' + MjpegMixin.mjpegBound)
        self.end_headers()
        self.wfile.write(MjpegMixin.frameBegin)

    def mjpegEndFrame(self):
        self.wfile.write(MjpegMixin.frameBound)


class SmoothedFpsCalculator:
    """
    Provide smoothed frame per second calculation.
    """

    def __init__(self, alpha=0.1):
        self.t = time.time()
        self.alpha = alpha
        self.sfps = None

    def __call__(self):
        t = time.time()
        d = t - self.t
        self.t = t
        fps = 1.0 / d
        if self.sfps is None:
            self.sfps = fps
        else:
            self.sfps = fps * self.alpha + self.sfps * (1.0 - self.alpha)
        return self.sfps


class Handler(BaseHTTPRequestHandler, MjpegMixin):
    def do_GET(self):
        if self.path == '/contour.mjpeg':
            self.handleContourMjpeg()
        else:
            self.send_response(404)
            self.end_headers()

    def handleContourMjpeg(self):
        import cv2
        import numpy as np
        width, height, blur, sigma = 640, 480, 2, 0.33
        fpsFont, fpsXY = cv2.FONT_HERSHEY_SIMPLEX, (0, height-1)
        self.mjpegBegin()
        with PiCamera() as camera:
            camera.resolution = (width, height)
            camera.video_denoise = False
            camera.image_effect = 'blur'
            camera.image_effect_params = (blur,)
            yuv = np.empty((int(width * height * 1.5),), dtype=np.uint8)
            sfps = SmoothedFpsCalculator()
            for x in camera.capture_continuous(yuv, format='yuv', use_video_port=True):
                image = yuv[:width*height].reshape((height, width))
                v = np.median(image)
                lower = int(max(0, (1.0 - sigma) * v))
                upper = int(min(255, (1.0 + sigma) * v))
                image = cv2.Canny(image, lower, upper)
                cv2.putText(image, '%0.2f fps' %
                            sfps(), fpsXY, fpsFont, 1.0, 255)
                self.wfile.write(cv2.imencode('.jpg', image)[1])
                self.mjpegEndFrame()


def run(port=8000):
    httpd = HTTPServer(('', port), Handler)
    httpd.serve_forever()


if __name__ == '__main__':
    import argparse
    parser = argparse.ArgumentParser(description='HTTP streaming camera.')
    parser.add_argument('--port', type=int, default=8000,
                        help='listening port number')
    args = parser.parse_args()
    run(port=args.port)

Install Debian 10 on Netgate SG-2220 via Serial Port with iSCSI Disk

Junxiao Shi — Sat, 06 Feb 2021 01:55:14 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2020/Debian-serial-iSCSI/

I get my hands on a Netgate SG-2220 network computer.
It comes preinstalled with either pfSense firewall software, or CentOS in the case of DPDK-in-a-box edition.
However, I'm more familiar with Debian based operating systems.
Can I install Debian on the Netgate SG-2220?

The Console Port

Hardware specification of the Netgate SG-2220 includes:

Intel Atom C2338 processor, dual core at 1.7 GHz
2GB RAM
4GB eMMC storage
one USB 2.0 port
two 1 Gbps Ethernet adapters

Notably missing is a VGA or HDMI port to connect to a monitor.
Instead, this computer offers a mini-USB "console port".
It is a UART serial port with a USB-UART bridge chip already included, unlike the C.H.I.P $9 computer that only provides serial over pin headers.

I plugged a USB cable to connect the "console port" to my Raspberry Pi, and a /dev/ttyUSB0 device showed up on the Raspberry Pi.
Then, I can type the following command to open the console screen:

sudo screen /dev/ttyUSB0 115200

iSCSI Target

Netgate SG-2220 has only 4GB storage.
This may be enough for a basic installation, but is insufficient for my use case.
Not wanting to permanently attach a USB hard drive, I decide to try something different: an iSCSI disk.

I learned (a little about) iSCSI in 2009 when I interned at Microsoft MSN.
iSCSI is a network protocol that allows one machine (called the target) to export a disk drive for use in another machine (called the initiator).
The initiator would see the disk drive as a block device (e.g. /dev/sdc), which can be partitioned using standard tools like fdisk or parted then formatted.

I followed How to Setup iSCSI Storage Server on Ubuntu 18.04 LTS to setup an iSCSI target on my Raspberry Pi.
The backing store is a 16GB file on an old 160GB USB hard drive.

Steps to Install Debian 10 on Netgate SG-2220

Before these steps, open the console screen and have the iSCSI target ready, according to last two sections.

Prepare a USB flash drive with Debian 10 "tiny CD" mini.iso image.
Plug the USB flash drive on the SG-2220, and connect the power cord.
BIOS screen should show up on the console screen, with a prompt "Press F12 for boot menu".
Press F12 and select "1. USB MSC Drive USB Flash Disk 1100".
When Debian installer menu appears, use arrow keys to highlight Install, then press TAB key.
The kernel command line should show up at the bottom of the screen.
Delete -- quiet at the end, then type console=ttyS1,115200n8 (this has to be typed one key at a time, pasting does not seem to work).
The next few steps are same as any other Debian installation.
Upon reaching the "Partitioning" step, select Manual partitioning method.
Then, select "Configure iSCSI volumes".

The installer would ask for the IP address, username, and password of the iSCSI target.
It then discovers available iSCSI targets.
Select our iSCSI target, and continue.

After that, it's time to create partitions.
The root partition (mount point /) should be placed on the local drive "3.8 GB Generic Ultra HS-COMBO".
The /home mount point goes on the iSCSI disk "IET VIRTUAL-DISK".
It would take about 20 minutes to get to the "Install the GRUB boot loader" step.
Select the local drive /dev/sda only.
The last screen of the installer is "Finish the installation".
Do not get too excited and hit the "Continue", because we still need to do a few adjustments.
Select Go Back, and then in the installer main menu select Start a shell.
Now we get a shell, in the installer's context.
To enter the "destination context" (installed Debian system), type these commands:
```
mount --bind /proc /target/proc
mount --bind /sys /target/sys
chroot /target
```

Change the kernel command line in the GRUB boot loader to use ttyS1:

vi /etc/default/grub
# change this setting:
#  GRUB_CMDLINE_LINUX="console=ttyS1,115200n8"

update-grub

Configure the iSCSI initiator to login automatically, and mark /home as a network drive:

vi /etc/iscsi/nodes/*/*/default
# change these settings:
#  node.startup = automatic
#  node.conn[0].startup = automatic

vi /etc/fstab
# for /home mount point, change mount options from "defaults" to "_netdev"

Move /usr/local and /usr/share to the iSCSI disk:
```
cd /usr
mv local ../home/usr-local
ln -s ../home/usr-local local
mv share ../home/usr-share
ln -s ../home/usr-share share
```
/usr/local is where I need more capacity in my use case.
/usr/share weighs 190MB and is not needed by the iSCSI initiator.
Type exit to return to the installer shell, type reboot to reboot into the installed Debian system, and quickly unplug the installer USB drive.

If everything went right, you'll see the login prompt in about a minute.

Mistakes and Lessons

I attempted the installation at least 5 times before getting the procedure right.
I'd share some mistakes I made, so that you can avoid them.

Ubuntu does not support installation via the serial port. Although I like Ubuntu more than Debian, I have to settle for Debian.
The mini-USB console port on the Netgate SG-2220 is ttyS1 as recognized by the Linux kernel. Thus, it's necessary to modify the kernel command line with console=ttyS1,115200n8. Without this setting, the kernel would use ttyS0 serial port, which might exist somewhere inside the computer but not accessible from USB-UART. This modification is needed both during installation and in the GRUB configuration of the installed system.
Debian's initial ramdisk does not support iSCSI initiator. Thus, putting the root partition (/ mount point) on the iSCSI disk will not work. The root partition has to remain on the local disk.
While the Debian 10 installer would write iSCSI initiator configuration to the installed system, it's configured with node.startup = manual. This default setting would cause "iSCSI login failed due to authorization failure" error. Both node.startup and node.conn[0].startup should be changed to automatic.
In /etc/fstab, partitions on the iSCSI disk must be marked _netdev. Without this setting, the system may attempt to mount the partition before the network is ready.