It is the first of these which I have recently been attempting and I think Phil Karlton might have a good point.
What are we talking about?Web browsers are pretty complex beasties but the basic concept is pretty easy to understand. They fetch a bunch of files that make up a web page and render those source files into something suitable for human consumption.
It is also intuitive that fetching all the files that make up a web page, every time you browse to a new page, might be wasteful, especially if most of the files had not changed from the previous page.
In order to address this browsers hang onto copies of these files in case your browsing needs them again, this is known as a source file cache. Caches are a
widely used technique throughout many aspects of computer technology but the basic idea is that they trade one resource for another.
In this case we are trading local storage space (memory or disc) for access time. This type of trade may give large benefits due to the
large differences in access times (sometimes known as latency) between local and network resources.
For example, if the source files that make up a web page are a Megabyte in size accessed with a 2013 era PC with a 10Mbit connection to the Internet:
- Accessing the data from main memory will take approximately 20 s (millionths of a second).
- The same data retrieved from a hard disc drive will take 4,000 s to arrive, around 200 times longer.
- If we were to retrieve the data from a fast web server and assuming the network connection is in perfect working order, the data will roll in 1,200,000 s later, or around 300 times more slowly than disc and a unfathomable 60,000 times slower than memory.
From this example it becomes startlingly obvious why a source cache is so desirable. I have greatly simplified the browsers operation here as they usually implement many layers of additional caching in other areas to make the browsing experience subjectively smoother.
And before the observant reader suggests that we could just make the network faster it ought to be mentioned that due to fundamental physical constraints, like the speed of light, it would be unlikely that the average practical network reply will ever drop much below 150,000 s [1] or some 40 times slower than disc. Still a worthwhile gain.
Knowing the cost of everything and the value of nothingHaving shown the benefits it might be nice to think there are no downsides to caching, this is not the case, as I mentioned we are trading storage for time and as in any trade one must expect there to be overheads.
In the case of a browser we face several obstacles. Firstly not every file that goes to make up a web page can be cached. The HTTP specification contains an
entire section on caching which contains numerous rules and operations to ensure that only objects that should be cached are and determines for how long they can be kept before going "stale".
A great deal of this complexity comes from just how desirable caching is to network providers. Many ISPs will have
web proxy servers to cache requests for all users to reduce their bandwidth usage, or increasingly, to implement content filtering according to the local government censorship rules. The browsers cache must know how to interact with these proxies without getting erroneous results.
Then comes the problem alluded to in the section title. A browsers cache cannot grow indefinitely. Eventually a system would run out of memory and disc if a browser kept every file. To deal with this the cache is limited sometimes by the number of files it holds, but more commonly by size both in memory and on disc.
The caching structure used by a web browser is hierarchical in that it will first evict (move) files from memory to a backing store (disc) and when the disc cache size limit is exceeded files are evicted to the next tier. Which in this case, will involve deleting the local copy (invalidating) and requiring performing a fetch from the network if the file is needed again.
When the cache size is exceeded the decision is made about what to remove from the cache using a
cache strategy or algorithm. The aim of this decision is to discard the data that will not be required again for the longest time.
If we had a blue box with a madman inside, who we could persuade to bring our browsing history back from the future, implementing
b l dy's algorithm might be possible. Failing a perfect solution we are reduced to making a judgement based on the information available to us.
This involves computing a cost for replacing each entry in the cache and evicting those with the lowest values. The selected algorithm has a large impact on the effectiveness of the cache and often needs fine tuning for the task at hand.
Never has so little been measured so muchHaving established that caching is useful and that we need to make decisions on what to keep it follows that those decisions must be based on information. This information consists of two main groups:
- A series of metrics about the cache state such as the number of objects and their cumulative size currently being stored in memory.
- Information about each object, known as metadata, this includes things like the objects individual size, how long until it becomes stale and when it was last used.
Maintaining all of this information is a significant part of the overheads involved with caching and a compromise must be struck between having the necessary information to make good caching choices and the cost maintaining that data.
Cache metricsMost cache implementations maintain at least some basic metrics, at the very least how much storage is being used so a decision on if evicting entries from the cache to reclaim space is necessary.
It is also common to keep a record of how well the cache is performing. The cache efficiency (the hit rate) is usually measured as the ratio of successful accesses provided from the cache (a cache hit) to the total number of requests to the cache.
A perfect cache would have all hits and no misses (a hit rate of 1) while using as little storage as possible (but as already noted that requires a special madman). The hit rate can be used to automatically change the behaviour of the eviction algorithm, perhaps using more storage if the hit rate drops too low or changing the eviction frequency.
MetadataEach object must carry with it the data necessary to regain its state when retrieved from the cache. This information is essential for the correct operation of the cache but in of itself provides no direct value.
In the case of browser source data this includes all the headers sent in the original network fetch. These headers are themselves just metadata sent along with the object by the web server which must be preserved.
Two particularly useful value for making a good eviction decision are how long it has been since the object was last used and how many times it has been used. This is because an object that was cached a long time ago and then never used again is much less valuable than one that has recently been repeatedly used.
An ImplementationIt is all very well talking about the general solution but a full understanding can only be gained by examining a real implementation. The
NetSurf cache was chosen as it is a suitably small amount of code but still demonstrates all the major design features.
InterfaceThe cache deals with all source data and provides the browser with a single unified object request interface regardless of if the source data can be cached or not. This is useful to hide the implementation details allowing for changes without affecting the rest of the browsers code.
The implementation effectively consists of two lists of objects, those that can be cached and those that cannot. Each object on these lists is reference counted against one or more users and while there is at least one user the source data is maintained in memory.
Objects determined to be non cached are always directly fetched from their source and are immediately released once they have no users remaining.
For cacheable objects an attempt is made to fulfil the request in descending order:
- from objects already in memory.
- from the backing store.
- from a network fetch.
Irrespective of the source of the data the remaining operations on the object (determining freshness etc.) are exactly as if the request had been fulfilled from the network. This approach means the use of the cache is transparent to the object users.
WriteoutObjects are placed in the backing store asynchronously to any other operations. When an object has been fetched from the network a background task is scheduled for when the browser is otherwise idle.
This writeout task constructs a list of all cacheable objects not yet in the backing store, associates a cost value with each object and then proceeds to write those objects to the backing store in highest to lowest value order.
CleaningA periodically scheduled task deals with ensuring the cache is cleaned. This consists of destroying stale objects and arranging fresh objects are not using more memory than the configuration permits.
Memory usage is reduced within the cleaning task by discarding the source data for objects already held in the backing store (where the data can be retrieved relatively cheaply)
Additional memory may be recovered by simply discarding unused objects held only in memory. These objects are usually those which have only recently become unused otherwise the writeout task would have committed them to the backing store.
The most recently used objects are statistically likely to be used again soon, because of this there is a high risk of a cache miss associated with discarding these objects. In order to mitigate this undesirable effect the cleaning heuristic favours using more memory than configured for short periods rather than discarding from memory.
Backing storeThe backing store is a simple
key-value database. Each source data object and its metadata (its headers etc.) is associated with a unique key (the URL used to fetch it). The backing store is simply required to store and retrieve the object data associated with the given URL.
The backing store implementation in NetSurf is pluggable, this flexibility is required for dealing with the greatly varying capabilities and limits of the various systems the browser is required to execute on.
A novel aspect of this backing store interface is that if an implementation returns the wrong object it is not considered an error and is simply treated as a cache miss. This is possible because the metadata contains the URL of the stored object enabling object verification.
This behaviour is permitted because techniques which significantly improve key-value store performance (principally
key hashing) become available if they are not required to always give the correct answer.
The backing store is also required to manage its size within the configured limits and deal with any filesystem behaviour details.
The reference backing store is trivial in that it performs a
hash operation on the input URL, encodes the result with base64url encoding and uses that as the object filename. The length of the hash can be configured allowing use of the reference implementation in any situation where using the filesystem as a database is acceptable.
The reference backing store default hash is
SHA-1 yielding almost unique [2] 160 bit key values stored in much the same way as the git DVCS. Note we are not using this hash for its cryptographic properties and at worst a collision will result in the cache being a tiny amount less efficient.
ConclusionHopefully this has shown what a browser source file cache is, why it is useful and a basic understanding of how they are implemented.
I will admit I have glossed over some of the more challenging aspects especially in relation to actually implementing the cache strategy but I hope that the reader will forgive those omissions of detail in a quest for a little more clarity of the general principles.
I would like to thank John-Mark Bell for implementing the NetSurf cache and to Melodie Parry for proof reading and providing feedback.
[1] Speed of light is 3x10^8m/s earth circumference is 4x10^7m, divide circumference by speed gives 133,000 s which gives longest round trip time from anywhere on surface of earth to point furthest from. So assuming a whole megabyte can be transferred in one round trip and allowing for some overhead the lower bound estimate of 150,000 s looks reasonable.
[2]
Mathematically speaking this hash would allow us to say that with the current estimated 1x10^11 URLs on the internet the likelihood of a collision is still vanishingly small (at least 1x10^-15)
(ARMv7 A15 dual core)
I ve covered how I set up my home LAVA lab and how I got two iMX.53 boards running, the next step was to sort out the LAVA server.
My initial setup relied on using my Thinkpad as the server. This was somewhat convenient as that s how I develop the code, but didn t help me run jobs like health checks because the laptop was usually somewhere other than on the home LAN. There had been a long-standing problem with using LAVA on ARM the uwsgi support didn t compile but the code being used was old. As the same code has been in Debian for a long time, I suspected that this was fixed with a newer version. So as part of migrating LAVA to django1.6, apache2.4, postgres9.3, django-tables2 0.13 and a few other updated dependencies, I have been using the version of uwsgi from Debian unstable for quite a while without problems on x86. A simple tweak to the LAVA setup scripts and a newer version of uwsgi became available and it builds just fine on armhf. (I haven t tried armel because Linaro is ARMv7 or newer and we don t test with ARMv5/ARMv6 boards, so there s no point in trying armel it s not likely to be an issue for this fix though.) (Only the current lava-deployment-tool methods need to actually compile uwsgi directly from upstream without any patches the packaging which will replace l-d-t uses precompiled binaries, just as any admin would expect.)
That initial install was on one of the iMX.53 boards, which ran as slowly as anyone who has used an iMX.53 would expect. I haven t run test jobs on that install, it had a hard enough time serving the frontend.
Clearly some more cores would be a good step and when an arndale became available for the home lab, the next step was to get a SATA drive onto the arndale, put Debian unstable on that and then deploy LAVA to the arndale using the Debian packages. As a bonus, these packages are built for django1.6 (using an unreleased branch).
Sounds simple enough. It works on iMX.53, it should work on an arndale. Well, it does but only after some unexpected faff.
arndale, u-boot and SATA
I hate u-boot every single time I ever touch it, the little I know about any other u-boot device is completely useless. Uniformity is a good thing infinite permutations are just rope to hang ourselves with cute embedded nonsense hacks and I m bored of that whole scene.
So, boot the arndale, interrupt the bootloader to get to the prompt. What s the first thing most people would want? help. Denied this particular u-boot has been compiled without the ability to display any help messages. u-boot has just sunk further into the depths of please can we have something else which is uniform across devices .
OK, well maybe I can get by without help. sata init unknown command sata . (Go away, do something else for a bit.)
The arndale isn t one of the newest boards in the ARMv7 world, LAVA has been using them for a while, so someone has probably done some work to fix this . nope. There s a workaround a nice detailed guide by Phil Endecott which details that the kernel needs to continue to be loaded from SD and then the SATA can be used for just the rootfs.
Mildly annoyed (I was hoping to be able to update the arndale kernel without the hassle of mounting the SD card at all), the rest was straight-forward.
Preparing the SATA and installing Debian
Due to the complexity of some of the transitions currently ongoing in Debian ahead of the Jessie release freeze, uwsgi is not in Debian testing right now so this install has to be Debian unstable. That s OK, I ve been running Debian unstable on all my machines for several years now usually updating ~5 times a week.
Zoe had Playgroup this morning. We had a little bit of time to kill between
when Sarah dropped her off and it was time to bike over to Playgroup, so we
went for a little walk to the post box to mail a letter. It was a beautiful
morning, so the walk was nice.
We biked over to Playgroup. Today I learned from the mother of the boy who was
causing issues last week, that he was extremely allergic to everything. They
couldn't use egg cartons for their craft activities, for example, because he
was allergic to eggs, and even the empty cartons would cause a problem,
apparently. That's quite the allergic sensitivity. I'm glad Zoe outgrew her egg
allergy.
Zoe wanted to do the craft activity first up, so she made another crown, this
time for Mummy. I helped roll scraps of crepe paper into balls, and she very
carefully glued them onto the points of the crown. She seems to really enjoy
mucking around with Clag glue pots. I'll have to get a bottle for home. It
reminds of my early primary school days.
After that, we just generally mucked around for the rest of Playgroup. She
loved the dress up pink lacy skirt again, and wanted to fool around on stage
for a bit.
One of my ex-co-workers has an occasional yum cha or laksa lunch with a bunch
of his ex-co-workers, and I was invited along to laksa at 
Each year the 
A new bug-fix / maintenance release 
As a followup for my 
Brief Glamor Hacks
Eric Anholt started writing Glamor a few years ago. The goal was to
provide credible 2D acceleration based solely on the OpenGL API, in
particular, to implement the X drawing primitives, both core and
Render extension, without any GPU-specific code. When he started,
the thinking was that fixed-function devices were still relevant, so
that original code didn t insist upon modern OpenGL features like
GLSL shaders. That made the code less efficient and hard to write.
Glamor used to be a side-project within the X world; seen as something
that really wasn t very useful; something that any credible 2D driver
would replace with custom highly-optimized GPU-specific code. Eric and
I both hoped that Glamor would turn into something credible and that
we d be able to eliminate all of the horror-show GPU-specific code in
every driver for drawing X text, rectangles and composited
images. That hadn t happened though, until now.
Fast forward to the last six months. Eric has spent a bunch of time
cleaning up Glamor internals, and in fact he s had it merged into the
core X server for version 1.16 which will be coming up this July.
Within the Glamor code base, he s been cleaning some internal
structures up and making life more tolerable for Glamor developers.
Using libepoxy
A big part of the cleanup was a transition all of the extension
function calls to use his other new project,
If that's what you're looking for, some variation on below may be of
use. In this approach, you build up a list of pages similar to the
paginator object page_range but with only the relevant pages
and the skip-markers identified.
If you ever find yourself doing a bit of technical support for relatives
over the phone, there's nothing like actually seeing what they are doing on
their computer. One of the best tools for such remote desktop sharing is
The next step on this front will be the addition of path-based
searches, using the excellent Postgres 
It seems that several people replied to the effect that they would pay people to take care of applying security updates, or even configuring adhoc things such as wikis, graphite, and MySQL.
Not enough people to rely upon, but perhaps there is scope for remote stuff being done in exchange for folding-money. (Of course some of those that replied are in foreign countries which makes receiving payment an annoyance, that's a separate problem though.)
Food for thought.
In the meantime I've settled into my use of 