Dynamic memory allocation has an important use in real world programs: data like input lines has no fixed size, so robust programs shouldn’t allocate fixed buffers for it. Writing a homework program I found another reason for it: it leads to more errors that tools like Valgrind can detect.

Using static allocation for such programs has its advantages: all size limits are specified, so it won’t cause errors like truncating input; it’s easy to declare static arrays of structures in C; it’s faster and doesn’t require many additional lines of code for deallocation of the structure nor thinking where to free the objects.

However, this approach makes debugging harder: static memory is valid for the whole run of the program. Tools like Valgrind’s Memcheck won’t complain about uninitialized values being read or memory being accessed after being freed. (There are problems that occur only with dynamic memory, like double frees or frees of unallocated memory, I don’t consider them as common or as hard as the issues that don’t depend on memory allocation style.)

(In real world programs another reason to use dynamic memory is that some of it might be returned to the operating system before the program finishes. This would be useful in long-lived processes doing big allocations for quick computations, although it won’t occur in all cases due to the way how malloc-style routines work.)

The program that motivated me to write this article implemented monotone polygon triangulation using the DCEL structure to represent the polygon. (This structure is not needed for this algorithm. Using it leads to having more bugs, therefore it is educationally useful.) The code managed half-edges to run an algorithm designed for vertices. Storing triangulated parts of the polygon was not needed, so they were deallocated immediately after printing their representation. This resulted in a use-after-free error detected by Valgrind, fixing it corrected an incorrect result on a different polygon. The code added diagonals between half-edges, the resulting graph wasn’t a correct triangulation if the diagonals were added between half-edges of different polygons: some of which were completely triangulated in some cases and thus deallocated before adding the faulty diagonal.

For nearly all my other programs I use languages with automatic memory management (and I don’t use data structures as complex as DCEL), so there would be no error with the deallocation delayed after the final use of the object. Previously I thought that all such errors would be introduced by incorrect placement of free or delete calls. This program helped me realize that the delete operator can be useful in detecting otherwise incorrect code.

The Lemote YeeLoong is a small and free software-friendly laptop and one of the few available non-x86 (and non-ARM) laptops. (It’s sometimes called a ‘netbook’ or a ‘mini notebook’.)

As a user and contributor to a GNU/Linux distribution supporting this device, I’m often asked about it. The information published by the manufacturer and distro maintainers doesn’t reflect what could be seen by a user. This review is based on my experience using it and questions of free software supporters interested in this device.

The YeeLoong I have is 8101B with a 10.1 inch display. The 8089B model probably differs only in display size (8.9 inch), having the same internals. There are newer YeeLoongs with 2G or 3A CPUs being marketed, these are significantly different on most points discussed here. (This review probably won’t be helpful for review-writing classes, there are better resources for them available.)

Hardware

Case

One of the most common marketing claims is that the machine was built by Quanta and the case is of high quality. This seems more reliable than most qualitative opinions stated on the Lemote page.

Shiny lid, the user-visible part matte, the parts I use aren’t visibly shinier. No intrusive logos (the small model name near the screen helps typing it correctly). No scratches after more than two years of using. The display hinge works ok.

(My other laptop, an Asus F3U has many scratches on top and had once many parts changed after the display hinge broke. Despite being newer by about a year, the parts I touched are now much shinier. Completely different experience.)

CPU

Loongson 2F is a single core MIPS3-compatible 64-bit CPU with some custom ISA extensions (not all used in software).

There is a custom SIMD extension, similar to MMX although not well-supported by GCC and with different intrinsics. A Gentoo hacker used them to optimize an important graphics library and posted a great explanation of these issues.

There are easily worked around bugs which would hang the machine (still untrusted code can do it), they were a bigger problem before English documentation was made available.

There is no uploadable microcode, this is one of the reason why x86 systems probably won’t be as free as this one (even the free boot firmware implementation coreboot usually requires nonfree CPU microcode).

The manufacturer claims of buffer overflow protection, this probably refers to an NX bit. I don’t know if it’s used in software.

Video card

The video card is a SiliconMotion SMI712 which does not have any hardware 3D acceleration. The reason why I consider the machine not completely supported by free software is limited 2D or video acceleration in free GNU/Linux distros.

gNewSense metad uses the fbdev driver without support for resolution change or 2D acceleration. Parabola uses the siliconmotion driver with unoptimal support for these features (fbdev is available). Newer X server releases make XAA slower (this is very noticeable when using KDE), while EXA hangs the machine (not a new issue), so fbdev might be faster now. There are legendary drivers with xrandr support, I never used them.

Gentoo has patches making full-screen low quality YouTube videos playable (I used WatchVideo for this), they probably could be ported to other distros. There are ongoing discussions on a new SiliconMotion video driver on the X.Org development list, maybe this driver will improve this situation (it has xrandr support).

The VGA output has low colour quality, although I haven’t used such outputs on other machines for a longer time, when all my other machines can use DVI-D. The documentation of the chip claims dual head support at 16 bpp, I never used it successfully.

SMI712 has only 4 MiB of video RAM, using reasonable resolutions might need special X settings to fit in it.

Summing up, I believe the only good thing about this chip is no dependency on a nonfree VBIOS, system-provided microcode nor driver. Unfortunately, no other graphics chip used in laptops or desktop computers known to me has this feature.

Display

Despite all the driver problems, this machine is fast enough to read typical books in a PDF reader. The screen is matte, unlike my other laptop, so it’s useful even during summer days.

However, decreasing the backlight brightness results in a headache-causing flickering (a problem caused by the LED backlight design, probably occurring on other devices). Usually I can use it at full brightness, it’s a less noticeable issue when not using X.

Wi-Fi

There are reports of the Wi-Fi card not working, but I haven’t observed any problems with it. AP mode is not supported by the driver, I never wanted to use it since my other machine with a more powerful Atheros 802.11n card supports it.

The card supports 802.11b and 802.11g, not 802.11a despite what some reviews state.

Webcam

The webcam works with only some programs, depending on kernel version. I probably haven’t tried enough to configure it.

SD card reader

It works with both SD and SD HC cards. Somehow on Parabola reading from the SD card was needed before the partitions were found, so it didn’t work well with the GUIs for mounting storage.

Booting from SD cards is not supported.

Touchpad

There is no middle button and the layout of left and right buttons make simultaneous clicks impossible.

The device is of Sentelic, it doesn’t support absolute positioning in the driver (possibly due to patent issues). I had better experience with an ALPS touchpad supported by the xf86-input-synaptics driver.

There are various non-mainline drivers for Sentelic touchpads (e.g. for MSI Wind), maybe some of them would work with the one in the YeeLoong. I haven’t tried using them.

Fan

It’s loud. It’s too often running, although this might be partially fixed using thinkfan.

RAM

Only 1 GiB is supported by the CPU and boot firmware. The SO-DIMM can be changed, I haven’t found any need to do it.

Disk

The (probably too optimistic in general case) hdparm benchmark shows 20 MB/s transfer speed, even when I configured the driver to consider it being connected via an 80 wire cable (a Parabola hacker had similar results with an SSD). The chipset and disk documentation suggests a much higher speed being supported. (Maybe this is related to using a SATA disk with an IDE controller?)

Suspend

Fan spins while suspended to RAM, so I use only suspend to disk.

Battery

The machine can work up to two hours on battery. The manufacturer claims lower power use of 12 Watts for the SSD version, data available to the system suggests it being similar for some uses of the HDD version.

Most netbooks work much longer on battery, this results from both bigger batteries and lower CPU power usage. Users who need this use external batteries (I never used them).

Connectors

The device has external connectors for VGA, power, 3.5 mm microphone and speaker, 100 Mbps Ethernet and three USB ports. Its layout prevents using both an Ethernet wire and an USB mouse (the wire would be on the place where I would keep the mouse), this doesn’t change mice being uncomfortable for me in all cases.

Boot firmware

The YeeLoong is often called the only laptop not requiring nonfree software. EC and hard disk firmware are exceptions.

All Lemote machines use a derivative of PMON2000 as boot firmware. It is free (under a four clause BSD license), although on all other devices than YeeLoongs with 2F CPUs it requires a sourceless VGA BIOS blob.

PMON initializes the hardware, shows a menu of kernels to run (using a GRUB 0.97-like configuration file) and boots one of them, supports network booting and flashing itself. It’s not compatible with x86 BIOSes and is more powerful (e.g. it can boot a kernel from an ext2 filesystem, although it doesn’t support newer filesystems).

Booting is fast unless using an initrd (gNewSense and Parabola kernels don’t need it unless using an encrypted root filesystem) or GRUB 2 booted from PMON (I see no benefit of using it).

It is also possible to use GRUB 2 as a PMON replacement, installed directly to a PLCC chip (coreboot doesn’t support the machine). It is difficult to solve potential problems with it due to the PLCC chip being soldered in most devices (or difficult to access).

Software availability

A Debian-based system with very old packages was installed on the machine. I haven’t used it long before installing gNewSense metad. (The installer was broken at that time, so I haven’t used it initially for two weeks before it was fixed; this problem motivated me to use IRC, this led me into contributing to several free software projects and using fully free GNU/Linux distributions.) The review at OSNews has more details on this system (and many other features that I haven’t noticed).

gNewSense has most Debian packages available. There is GHC without the interactive interpreter and a slow Java implementation (without JIT). Mono and Valgrind are not available (although the newest release of Valgrind supports MIPS and is included in Debian Jessie). Gnash is available, although it is too slow to be useful for me and there are better specific tools for most tasks that I could need it for.

While Debian and gNewSense use packages built for any little-endian MIPS system, Parabola has them optimized for Loongson 2F and uses a different ABI called N32 that uses 64-bit registers (and all floating point registers, unlike O32 used in Debian) while 32-bit pointers are used (so a single process can use only 2 GiB of virtual memory: the highest address bit is used for kernel and physical memory). As an advantage, some articles suggest it being 30% faster on some operations. A disadvantage is lack of support for many architecture-specific packages like Java, Valgrind or GHC (and much more portability problems in other packages like WebKit which doesn’t need to use architecture-specific code). Now more packages start to require a JIT, so modern Mozilla software and Qt 5 aren’t available on N32.

One of the reasons for RMS to use such a machine is that it is not supported by popular nonfree operating systems, so it won’t be used to promote them, unlike OLPC.

Performance

The CPU speed is not a problem unless compiling distro packages or using Java or other programs that are optimized for JIT not available or working on the MIPS ABIs used (or when playing videos without large assembly patches using its SIMD extension).

Building GCC, Mozilla browsers or WebKit is too slow to maintain these packages correctly in Parabola. Typical tasks like Web browsing are interactive enough, unless building a package at the same time or viewing a big JPEG image (although this is also slow on my AMD64 machine).

Having played free games like Wesnoth, FreeDink and DCSS (without tiles which require hardware-accelerated OpenGL), I’m not convinced that good games need 3d acceleration.

Availability

There were YeeLoongs available in Europe from Tekmote Electronics (where I bought mine from) and KD85.com. Freedom Included was selling them in the USA with gNewSense preinstalled.

The manufacturer site claims of ‘very competitive price’, this certainly isn’t true in Europe in comparison with non-freedom-respecting x86 netbooks.

Summary

I know three main reasons to use a YeeLoong: it respects user’s freedom, it can be used for MIPS programming and it is a small and portable laptop. I don’t know any good alternatives for the first two of these uses. Except for the graphics performance, I believe the YeeLoong might still be an appropriate device as a general purpose small laptop (although this is not a significant problem for most of my text-oriented needs).

A common misconception about free software is that having a free license is both a sufficient and necessary condition for the software to be free. There might be cases when software is too simple to be restricted by copyright, so it is not a necessary condition. There are much more important arguments why it is not sufficient.

Copyright is used to restrict sharing of a work. This is often used to prevent users from cooperating with other users, while this can be used to prohibit some restrictions of the freedom of derivative work users in a practice called copyleft. Although copyleft can limit freedom of users modifying software (works under different copyleft licenses usually cannot be merged in one derived work), this is practically a useful compromise which won’t be discussed in this essay.

The most obvious way to restrict user’s freedom is to not share with them a source form of the program. There are many sourceless blobs of microcode in the kernel called Linux, while they have free licenses ‘giving’ users freedom that they cannot use. Without copyright (or with a very short one), there would be no effect on restrictions of nonfree software, only copyleft would be limited. Digital restrictions management clearly shows that copyright isn’t important for software owners: they make and enforce their own rules restricting what the user can do (actions allowed by copyright laws are also restricted by DRM).

DRM wouldn’t be effective if the user could understand the program (difficult, although possible even without source code as some cases in cryptography show) and install a different one. The second part is prevented by nonmodifiable bootloaders that can load only software signed by the device manufacturer. This is a common practice for phone and tablet operating systems using much GPLv2-licensed software, named tivoization after an early case.

Although free software licenses can protect users from the above problems in derived works, there are different legal issues that won’t be avoided in this way. Software patents are one of them. Governments censoring useful cryptography or pornography are similarly a restriction of software user’s freedom (and non-user’s).

These examples show that free software licenses aren’t sufficient for software to be free, while they don’t suggest any obvious solutions to this problem. They clearly require user’s awareness of their (not necessarily software-related) freedom. The focus on licensing leads to them not considering these issues restrictions of their freedom. It could also limit the visibility of copyright problems making other alternatives (with appropriate replacements for copyleft) more beneficial in a longer term.

We often see diagrams called ‘trees’ showing how different beings or things evolve from others. These are used to describe families, species, languages, programs and other entities. Most of them share two problems: they aren’t trees as in graph theory (while we reason about them as trees) and they don’t have discrete, unchanging nodes.

Directed acyclic graphs of evolution

Let’s assume for a while that there are immutable objects with derivative objects being created in atomic ways. These objects are nodes (or vertices), there are edges connecting them from the base one to the derived one.

The ‘tree’ will have nodes with multiple outward edges. However, in many real cases it will also have multiple inward edges. It isn’t a tree, the graph theoretic name for it is a directed acyclic graph, or a DAG. (We won’t get cycles by just adding immutable nodes having immutable lists of predecessor nodes, which seems all what we can do with unidirectional time and really atomic objects.)

Probably the most famous DAGs called ‘trees’ are ‘family trees’. The larger and more complex ones aren’t trees, there is a newer example in The Art of Computer Programming by Donald E. Knuth, Volume 1 Third Edition, Figure 18(a) on page 310 (the family DAGs of Eldar or Edain in the books of J.R.R. Tolkien are more interesting cases, although improbable without elven lifespans). Some have ancestors aligned on layers depending on the distance from a descendant, these might have multiple nodes on different layers for the same person. It’s an obvious consequence of every person having approximately two parents and there not being exponentially more people several generations ago. As explained in the TAOCP (page 311), these graphs are trees if a node represents ‘a person in the role of mother or father of so-and-so’ (I haven’t seen this definition anywhere else).

There are more software-related examples of graphs not being trees (leaving other natural examples for the next section, since they don’t have obviously atomic nodes). Dependencies graphs of classes, modules and software packages (being specific sets of code, so they are atomic as considered in this article) clearly aren’t trees in general (and common) case. (Dependencies inside a package are often cyclic and this isn’t usually a problem. It is more difficult in case of dependencies between packages, compilers are a well-known case of this.) I believe the assumption that software packages dependency graphs are nearly always trees, optimizing the design of software using such graphs for this case and adding workarounds for a package occurring in multiple parts of the ‘tree’ leads to a much more complex solution than designing for a DAG.

A significantly different tree-vs-DAG understanding issue is that software doesn’t evolve in trees. A common free software ideology point of view is that the user gets a software package, modifies it using only their own ideas and publishes it. This isn’t true, a common and important case is deriving a new package (or technically a version of the package, both are equally nodes here) from multiple other packages. Nearly any use of shared libraries from multiple projects is a case of this. This leads to different software freedoms than the tree view (the Free Software Definition mentions this way of modifying programs, although accepts licenses restricting what licenses the original programs can be under; I see no solution for this better than using only GPL-compatible licenses for all cultural works).

(There is also an interesting, although unrelated to trees, issue of maps being nonplanar graphs. I don’t remember seeing an example of a map having its chromatic number greater than four, although there are many cases requiring four colours. Many countries in these cases are non-contiguous, so a graph of a map containing them doesn’t have to be planar.)

Are there atomic nodes?

In the above examples it was clear what objects were nodes. Each edge referred to complete atomic nodes (e.g. there are parents of a human, not of their specific organs, I don’t know any other cases than aren’t only medically significant unlike the probable uses of family ‘trees’). It isn’t in all common uses of ‘trees’. If the node refers to a mutable union of immutable objects (or a mutable object), the graph can easily have cycles, multiple edges between the same nodes (it even is’t usually called a graph), or just be too unclear to be useful.

A problem of such nodes is that we often don’t know clearly when we have the same node.

Probably the most well-known example is a phylogenetic tree showing a common origin of species (this isn’t the only evolution the title of this article refers to). As described in that article, the ‘ideal’ approximated by such trees isn’t a tree, due to interesting issues like horizontal gene transfer which clearly makes it not a tree. Another issue is that there is no clear separation between species.

The same problem occurs in the evolution of languages. There is no clear separation between languages (except for the political ones). If, in parallel to the definition of a species as a set of animals being able to have common descendants, we define a language as a set of mutually-intelligible sentences, there is no point of separating languages (for each pair of communicators there is at most one language, there is no observable way of finding which of these languages are ‘the same’; this might be a reason for other definitions being widely used).

There is a similar case for software evolution. There is a great graph of GNU/Linux distribution derivation. Since the distributions change, it has many vertical lines when a distribution e.g. changes its base distribution. Somehow this case avoids having the nodes as unclear as species or languages.

Let’s not call the next graph a ‘tree’, unless the objects being modeled are clearly separate, atomic and form trees, not more complex graphs.

DNS solves two problems:

1. translating between human-readable domain names and machine-usable IP addresses
2. storing a reliable, hierarchical, distributed database describing which servers provide which services and the above mapping.

It’s known that the second problem is solved inefficiently, insecurely, unreliably and centrally. Thus a different system should be designed to solve it without these problems.

The first problem is solved using globally unique names with unique meanings. This is an unreal assumption enabling useless or harmful activities like domain parking, domain squatting, trademarks being used for censorship, or just making the names difficult to type.

This probably contributes to the fact that users often use machines to store the domain names. Other issues like advertising contribute to using unreadable names and sharing them via e.g. QR codes instead of memorization by humans.

Therefore I believe a good replacement for DNS solving the second problem would not use globally unique human readable names.

Let’s assume that a single being manages the database fragment describing some machines (like a DNS zone). There is no problem with having names in the fragment. The fragment should be signed using a key pair used only for this zone with private part known only to the managing being. Probably any useful and scalable DNS alternative would do this.

The ‘name’ of the zone would be the public key used to sign the zone. It would be random-like and there practically wouldn’t be multiple zones with the same ‘name’, so this would avoid the problems of nonrandom unique names. There are algorithms using elliptic curve cryptography having good enough public keys small enough to use them in a DNS domain name, they could be used here (although having e.g. a multi-kilobyte zone ‘name’ wouldn’t be a problem for machines transferring them).

We could let anyone serve the zone data, since knowing the public key allows knowing if the untrusted server provided us the correct data, assuming the data doesn’t change. In real life such data changes, but having an outdated copy could be detected by e.g. specifying the time when the data is valid in the zone (DNS uses a similar solution, although it wouldn’t need having globally synchronized clocks). There are existing solutions for sharing such data without having a central server.

This leaves the problem of having human-typeable names for the zones in the rare cases when they are useful. This would be solved by having a local daemon having such user-specified mapping and maybe asking other such daemons for other names (e.g. if the user has many machines or uses names shared with other users in a single organization).