Linux Inside – A book-in-progress about the Linux kernel and its internals

Linux Inside” is a book-in-progress about the Linux kernel and its internals.  You can read it online or download as a PDF.  It’s also available in several languages.  Some of the things that you’ll find inside are:

  • The boot process
  • Initialization
  • Interrupts
  • System calls
  • Timers and time management
  • Synchronization primitives
  • Memory management
  • SMP
  • Data structures in the Linux kernel
  • … and more.

 

Netsim – a network simulator game for teaching

Netsim is a simulator game intended to teach you the basics of how computer networks function, with an emphasis on security. You will learn how to perform attacks that real hackers use, and see how they work in our simulator!

Netsim is completely free to play.

JPEG Huffman Coding Tutorial

I came across this rather useful and practical tutorial on Huffman Coding in JPEG images.  It looks at a very small and basic black-and-white image, and how the size of the data and overhead changes between different image formats, and then in more detail, how the Huffman Coding helps make that happen.

Unless you are dealing with compression, image formats, and binary trees on a daily basis, this tutorial is a good memory refresher of those college days.

350+ Data Structure Problems with Solutions

Here is a rather extensive collection of 350+ data structure problems with solutions.  The list varies from the usual searching and sorting of values in an array, to string manipulation, binary logic, matrices and graphs.  No matter how high was your grade for all those Computer Science courses back in college, or how long have you been programming, I guarantee you’ll find a challenge or two in this list.

From a very brief couple of hours look at the list, my favorite ones seem to be around the chessboard problems, such as this chess knight problem for finding the shortest path to destination using a queue.

What are some things you wish you knew when you started programming?

Quora thread on “What are some things you wish you knew when you started programming?” is a goldmine of wisdom.  Irrelevant of how experienced you – whether you’ve been programming for decades or just thinking about a new career path, which programming languages and technology stacks you use, whether you’ve completed format education or taught yourself everything you know, I’m sure you’ll find valuable lessons and food for thought in there.

Source Making : Design Patterns

Source Making does an excellent job with a few subjects.  The one I found particularly useful over the last couple of days is Design Patterns.  Not only the explanations are simple and straight to the point, and with a handy example, but they also clarify the differences between a pattern in question and a few similar patterns.

Design Patterns for Humans

Design Patterns for Human is an excellent effort to explain design patterns in plain words and simple examples.

Design patterns are solutions to recurring problems; guidelines on how to tackle certain problems. They are not classes, packages or libraries that you can plug into your application and wait for the magic to happen. These are, rather, guidelines on how to tackle certain problems in certain situations.

This collection is useful both for novices who are just trying to figure out what design patterns are and how to use them, and experienced developers who need a quick reminder once in a while.  Shorter than a book, simpler than Wikipedia.

Top 29 books on Amazon from Hacker News comments

hacker-news-books

I came across this nice visualization of “Top 29 books ranked by unique users linking to Amazon in Hacker News comments“.

Amazon product links were extracted and counted from 8.3M comments posted on Hacker News from Oct 2006 to Oct 2015.

Most of these are, not surprisingly, on programming and design.  A few are on startups and business.  Some are on how to have a good life.  Which is a bit weird.

Dependency resolution with graphs in PHP

One of the projects I am working on at work presented an interesting problem.  I had a list of items with dependencies on one another and I needed to figure out the order in which to use those items, based on their dependencies.

For the sake of the example, think of a list of database tables, which reference each other.  I need a way to export those tables in such a way, that when imported back in, tables that have dependencies will be imported after all those tables on which they depend.  (It’s not the real task I’m working on, but close enough.)

Consider the following list as an example of input data:

// List of items with dependencies.  Order is not important
$tables = [ 
    'articles_meta' => ['articles'],
    'articles' => ['users', 'categories', 'tags'],
    'categories' => [],
    'comments' => ['users', 'articles'],
    'options' => [],
    'tags' => [],
    'users' => [],
    'users_meta' => ['users'],
];

The result of the dependency resolution should give me the list like this (there are variations in order, of course, as long as the dependencies are satisfied):

categories
options
tags
users
users_meta
articles
articles_meta
comments

There are several ways to solve this problem.  My first attempt took about 50 lines of code and worked fine, but it lacked elegance.  It had too many nested loops and tricky conditions and was difficult to read.  My second attempt was slightly better, with a bit of a recursion, but still looked somewhat off.  It felt like there is a better way to do it, and that I’ve done something similar before, but I could put my finger on it.

I thought I’d take a look at something that solves a similar problem.  Composer, PHP package and dependency manager, surely had something to offer.  A brief check of the GitHub repository, and that idea is out of my hand.  Composer deals with much more complex issues, so its Dependency Resolver code is not something I can grasp in a few minutes.

It was time for some Googling.  Moments later, my deja vu feeling of “I’ve seen this before” was easily explained.  This problem fits into the graph theory, which I probably used last back in my college years.  Of course, I could have grabbed the book off the shelf and refresh my knowledge, practicing the sacred art of the Real Programming.  But time was an issue, so I cheated.

I found this “Dependency resolving algorithm” blog post by Ferry Boender over at Electric Monk (thanks man!).  He had exactly what I needed – simple and straight forward recursive algorithm for walking the graph, circular dependency detection, and even some performance optimization.

dep_graph1

The only problem was that his code is all in Python.  But that’s not really a problem.  So I’ve rewritten his code in PHP and got exactly what I needed.  Here it is:

// List of items with dependencies.  Order is not important
$tables = [
    'articles_meta' => ['articles'],
    'articles' => ['users', 'categories', 'tags'],
    'categories' => [],
    'comments' => ['users', 'articles'],
    'options' => [],
    'tags' => [],
    'users' => [],
    'users_meta' => ['users'],
];

$resolved = []; 
$unresolved = []; 
// Resolve dependencies for each table
foreach (array_keys($tables) as $table) {
    try {
        list ($resolved, $unresolved) = dep_resolve($table, $tables, $resolved, $unresolved);
    } catch (\Exception $e) {
        die("Oops! " . $e->getMessage());
    }   
}

// Print out result
foreach ($resolved as $table) {
    $deps = empty($tables[$table]) ? 'none' : join(',', $tables[$table]);
    print "$table (deps: $deps)\n";
}

/**
 * Recursive dependency resolution
 * 
 * @param string $item Item to resolve dependencies for
 * @param array $items List of all items with dependencies
 * @param array $resolved List of resolved items
 * @param array $unresolved List of unresolved items
 * @return array
 */
function dep_resolve($item, array $items, array $resolved, array $unresolved) {
    array_push($unresolved, $item);
    foreach ($items[$item] as $dep) {
        if (!in_array($dep, $resolved)) {
            if (!in_array($dep, $unresolved)) {
                array_push($unresolved, $dep);
                list($resolved, $unresolved) = dep_resolve($dep, $items, $resolved, $unresolved);
            } else {
                throw new \RuntimeException("Circular dependency: $item -> $dep");
            }
        }
    }
    // Add $item to $resolved if it's not already there
    if (!in_array($item, $resolved)) {
        array_push($resolved, $item);
    }
    // Remove all occurrences of $item in $unresolved
    while (($index = array_search($item, $unresolved)) !== false) {
        unset($unresolved[$index]);
    }

    return [$resolved, $unresolved];
}

Running the above code produces the following result:

$ php dependecy.php 
users (deps: none)
categories (deps: none)
tags (deps: none)
articles (deps: users,categories,tags)
articles_meta (deps: articles)
comments (deps: users,articles)
options (deps: none)
users_meta (deps: users)

Which is exactly what I was looking for.  And now that I have it here, I’ll probably be needing it again and again.  It’s an elegant hammer to a lot of my nails.