Introducing plan: The Time Management System for Illumos Propeller Heads

This entry is still a work in progress, will change often.

(UPDATE: Sept. 2014): The software itself is in a state of stagnation. I am working a newer, less crufty, less buggy, more general time-management system, that will be released soon.

I have always found that planning is useless, but plans are indispensable.
-Dwight D. Eisenhower

Using the idea of resource allocation, I’ve created plan, a nifty command
line application that automatically schedules activities based on how long they
last, and when they should start. A truly automated digital replacement for the
much-hated daily planners. Other digital planners just digitize the tedium of
laying out your day. Replace your daily planners! Unix style.

Recently I came to the morbid realization that I had to manage my time, if I
wanted to get anything (besides programming) done. Upon realizing this most
unfortunate truth, I cried a little, found some graph paper, and shaded out the
grid, so that my weekly schedule would be apparent upon glimpsing at it. Sadly,
there was significant resistance from my stubborn circadian rhythm, which
wouldn’t allow me to wake up quite as early as I would have liked.

Instead of re-shading another piece of graph paper, I gave in and tried using
Google Calendar. It’s a very cute web application. Where “cute” is a euphemism
for “my grandma might like it”. And yet, despite its simplistic
point-click-drag paradigm, it was far too manual for my taste. But it got the
job the done, and I was actually managing my time. I was a living oxymoron.

Unfortunately, I have problems. More specifically, I have problems with the
implication of having a web-based time management system. The implication is
that time management is useful if you have an internet connection, and
unnecessary if you don’t. No connection, no Google Calendar, no time
management. And my connection isn’t exactly persistent because I also have
problems with my university’s IT department.

I could have found a local TMS. But that presents another problem, endemic
to all of today’s TMSs. Namely repetition. Modern TMSs present the user with a
calendar that spans infinitely (practically speaking) into the future, and
allows the user to mark it up with a point-and-click interface. The first
problem is the fact that you have to use the mouse. Compared to typing on the
keyboard, the mouse is dog slow, and its use should be reserved for very
specific activities like photo editing. The second problem is that these TMSs
don’t differentiate between activities that have a starting time and a
duration, and todos that merely have a due time. The last problem is that
these TMSs fail to take into account is that most of our activities follow a
repetative weekly routine, but diverge on certain dates. For example, in
college, my class schedule is weekly, but my Calculus class is cancled on
11/09/19 (I wish).

Also, my problem with graphical applications (and thus web applications), is
that they are not integrated with Unix. Graphical applications can’t be piped
into grep or awk. Sure they can be scripted (look at Firefox), but these
scripts likely aren’t reuseable with other applications (or even with other
scripts in the same application). Scriptable graphical applications create
walled gardens, hinder code reuse, and generally waste my time by forcing me
to be redundant and manual. And besides, I don’t know of any local graphical
TMS that is scriptable.

The Unix command line is perfection. And I won’t settle for anything less.

In the name of truly efficient time management, I’ve created a command line
application, named plan. First, I’ll demonstrate what it’s capable of, then
I’ll go into its implementation.

Introduction and Demonstration

It’s a single command that does the following:
* allocates activities on a per-day and per-date basis
* establishes todo’s on a per-day and per-date basis

When an activity is allocated on, say, Sunday, it is understood that it repeats
every Sunday. However when that activity is allocated on (11-09-18), it is
understood that it only ever occurs on (11-09-18). The same applies for todos.

Creating and Destroying Activities and Todos

We can create activities and todos either on a given weekday, or on a
particular date.

Here we create an activity on Monday, called class_calc.

#plan create Mon/class_calc

As you can see, day names can be abbreviated. ‘Monday’, ‘Mon’, ‘monday’, and
‘mon’, all refer to the same week day.

We’ll also create a todo called hw_calc, which also occurs on every Monday.

#plan create Mon/@hw_calc

Todos are always prefixed with an ampersand (@).

Also, we can create a general todo, which is a todo that has no specific day,
date, or time.

#plan create @go_skydiving

The general gist of general todos is “I have to do this anytime between now,
and the day I die”.

For the sake of populating more than just one weekday, we’ll also create an
activity on Tuesday called class_db (my databases class):

#plan create Tues/class_db

Creating a random activity on a specific date:

#plan create 11-10-09/random_activity

We can also specify the previous command as:

#plan create 11-Oct-09/random_activity

or:

#plan create 2011-Oct-09/random_activity

and so on.

To destroy an activity or todo, we replace create with destroy in the above
commands.

Listing Activities and Todos

First, let’s list all of the activities that occur on Monday.

#plan list -a Monday
(0/1440)
NAME                    DYN    TIME     DUR
class_calc             true     N/A  00h00m

The -a specifies that we want to list activities.

So, we have one activity, class_calc.

The first line of output indicates the ratio of allocated minutes to available
minutes on this particular day. The second column, DYN may be enigmatic at
first. It’s a boolean that indicated whether or not an activity is dynamic. A
dynamic activity has a duration, but no explicit starting time. Dynamic
activities have their starting time assigned by plan.

The third column, indicates that the starting time is not yet assigned. The
fourth one indicates that the duration is zero. When an activity has no
duration, it is effectively unallocated.

Now, let’s list all of the activities that occur over a generic week.

#plan list -a week
Monday
(0/1440)
NAME                    DYN    TIME     DUR
class_calc             true     N/A  00h00m

Tuesday
(0/1440)
NAME                    DYN    TIME     DUR
class_db               true     N/A  00h00m

So that’s pretty neat, we can see our weekly schedule.

But it gets better. We can also display the weekly schedule for the current
week which will, replace week days that diverge from the weekly routine, as a
result of creating an activity on a date that this week overlaps with. As you
can see this week diverges from our generic weekly routine (namely, Sunday has
a random activity).

#plan list -a this_week
Sunday (2011-10-09)
(0/1440)
NAME                    DYN    TIME     DUR
random_activity        true     N/A  00h00m

Monday (2011-10-10)
(0/1440)
NAME                    DYN    TIME     DUR
class_calc             true     N/A  00h00m

Tuesday (2011-10-11)
(0/1440)
NAME                    DYN    TIME     DUR
class_db               true     N/A  00h00m

Sometimes, we may want to display the schedule (or todos) for next week, in
which case may do the following. The next week is the same as any generic week.

#plan list -a next_week
Monday (2011-10-17)
(0/1440)
NAME                    DYN    TIME     DUR
class_calc             true     N/A  00h00m

Tuesday (2011-10-18)
(0/1440)
NAME                    DYN    TIME     DUR
class_db               true     N/A  00h00m

We can view todos in much the same fashion.

#plan list -t week
NAME                   TIME 
hw_calc               00:00
#plan list -t this_week
NAME                   TIME 
hw_calc               00:00
#plan list -t next_week
NAME                   TIME 
hw_calc               00:00

Since we have not created any todos that on a particular date, instead of a
week day, the three above commands share the same output.

Durations, Starting Times, and Awake Times

Let’s attempt to put a starting time on class_calc.

#plan set time=08:35 mon/class_calc
Monday: Can't set time on activity class_calc. Activity doesn't have duration.

What you’re seeing now is an error. plan won’t set a starting time on an
activity if it has a duration of 0 minutes. plan essentially allocates time
to activities and resolves conflicts between activities. We just asked it to
allocate nothing, which is bogus (think umem_alloc(0, flag), which always
returns NULL).

We’ll have to set the duration first.

#plan set duration=01h15m mon/class_calc
#plan list -a mon
(95/1440)
NAME                    DYN    TIME     DUR
class_calc             true   00:00  01h35m

So class_calc now has a duration and starts at 0:00 (12:00 am), because that’s
the earliest time at which it can possibly start.

However, we can change that, by setting the awake property for Monday.

#plan set awake=07:00,16h00m mon
#plan list -a mon
(95/960)
NAME                    DYN    TIME     DUR
class_calc             true   07:00  01h35m

Setting a wake-up time changes when the day starts. If the day doesn’t start
before 07:00, it makes no sense to have the class_calc activity start at 00:00 (as
we’re asleep). So plan automatically adjusted it to start at the earliest
possible time.

Now let’s try to set the starting time again.

#plan set time=08:35 mon/class_calc
#plan list -a mon
(95/960)
NAME                    DYN    TIME     DUR
class_calc            false   08:35  01h35m

Yay, it worked. And now, the class_calc activity is no longer dynamic. Which
means that it can’t be automatically moved to a different block of time if
there is a conflict.

Let’s test this. What happens if we try to set the awake property to one hour
after my Calculus 2 class starts?

#plan set awake=09:35,16h00m mon
Monday: Activity class_calc can't fit in the alotted time
#plan list -a mon
(95/960)
NAME                    DYN    TIME     DUR
class_calc            false   08:35  01h35m

As you can see, we can’t set the awake time on Mondays to 9:35, because class_calc
starts an hour before that! And because class_calc is not dynamic, we can’t
move it. As the list command indicates, we didn’t change anything. The
16h00m indicates that this day lasts for 16 hours. There are limitations:
waking up at 13:00, would prevent you from having a day that lasts for more
than 11 hours. The reason this limitation exists, is that even though I can
implement a day that starts at 13:00 and lasts 16 hours, I wouldn’t be able to
wrap an activity, that lasts say 3 hours, and starts at 23:00, around the end
of the day, due to an implementation detail. And besides, that would encourage
the wrong kind of behaviour!

Sometimes allocating time to an activity will fail because there isn’t any free
block of time that is big enough for the activity. If this activity is, say
01h30m (and it doesn’t need to be contiguous), we can always split it into 2 or
three chunks like so:

#plan set duration=00h45m*2 [[activity-name]]

or

#plan set duration=00h30m*3 [[activity-name]]

Note that a chunked activity can’t have an explicit starting time.

Renaming Activities and Todos

So, class_calc represents my Calculus 2 class. But I think class_calc2
would be a more apt name for it. I can rename it using the rename subcommand.

#plan rename mon/class_calc mon/class_calc2
#plan list -a mon
(95/960)
NAME                    DYN    TIME     DUR
class_calc2           false   08:35  01h35m

My Weekly Schedule

Here’s the weekly schedule that I follow. It was entirely generated by plan.
I must say, that I’m far more productive now than I’ve ever been.

Sunday
(990/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
study_calc             true   06:30  02h00m
study_algs             true   08:30  03h00m
brunch                false   11:45  00h30m
study_db               true   12:15  03h00m
study_calc             true   15:15  01h00m
dinner                false   16:30  00h30m
prj_zaps               true   17:00  02h00m
study_csoc             true   19:00  01h00m
study_phys             true   20:00  03h00m

Monday
(890/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
prj_zaps               true   06:30  01h00m
breakfast             false   07:30  00h30m
class_calc2           false   08:35  01h35m
prj_zaps               true   10:10  01h00m
class_algs            false   11:25  01h15m
lunch                 false   12:40  00h30m
study_phys             true   13:10  01h30m
study_db               true   14:40  01h30m
dinner                false   16:30  00h30m
study_algs             true   17:00  01h30m
study_calc             true   18:30  01h30m
prj_zaps               true   20:00  02h00m

Tuesday
(850/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
prj_zaps               true   06:30  01h00m
breakfast             false   07:30  00h30m
study_phys             true   08:00  01h30m
class_db              false   10:00  01h15m
lunch                 false   11:20  00h30m
study_algs             true   11:50  01h30m
class_phys            false   13:50  01h15m
prj_zaps               true   15:05  01h00m
dinner                false   16:30  00h30m
prj_zaps               true   17:00  00h30m
study_calc             true   17:30  00h45m
lab_phys              false   18:25  02h40m
study_calc             true   21:05  00h45m

Wednesday
(865/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
study_phys             true   06:30  00h45m
breakfast             false   07:30  00h30m
study_db               true   08:00  00h30m
class_calc            false   08:35  01h15m
study_algs             true   09:50  01h30m
class_algs            false   11:25  01h15m
lunch                 false   12:40  00h30m
study_db               true   13:10  00h30m
lab_calc              false   13:50  01h15m
study_phys             true   15:05  00h45m
study_db               true   15:50  00h30m
dinner                false   16:30  00h30m
study_calc             true   17:00  00h45m
class_csoc            false   18:25  02h40m
study_calc             true   21:05  00h45m

Thursday
(930/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
prj_yacc               true   06:30  00h30m
breakfast             false   07:00  00h30m
prj_zaps               true   07:30  02h00m
prj_yacc               true   09:30  00h30m
class_db              false   10:00  01h15m
lunch                 false   11:20  00h30m
study_db               true   11:50  01h30m
prj_yacc               true   13:20  00h30m
class_phys            false   13:50  01h15m
prj_zaps               true   15:05  01h00m
dinner                false   16:30  00h30m
study_phys             true   17:00  01h30m
study_algs             true   18:30  01h30m
study_calc             true   20:00  01h30m
prj_yacc               true   21:30  00h30m

Friday
(1020/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
prj_yacc               true   06:30  01h00m
breakfast             false   07:30  00h30m
prj_yacc               true   08:00  00h30m
class_calc            false   08:35  01h15m
study_calc             true   09:50  01h30m
class_algs            false   11:25  01h15m
lunch                 false   12:40  00h30m
study_algs             true   13:10  01h30m
prj_yacc               true   14:40  01h00m
prj_zaps               true   15:40  00h30m
dinner                false   16:30  00h30m
study_calc2            true   17:00  01h30m
study_phys             true   18:30  01h30m
study_db               true   20:00  01h30m
prj_zaps               true   21:30  02h00m

Saturday
(930/1080)
NAME                    DYN    TIME     DUR
shower                false   06:00  00h30m
study_calc             true   06:30  02h00m
study_algs             true   08:30  03h00m
brunch                false   11:45  00h30m
study_phys             true   12:15  03h00m
study_calc             true   15:15  01h00m
dinner                false   16:30  00h30m
study_csoc             true   17:00  01h30m
study_db               true   18:30  03h00m
prj_zaps               true   21:30  00h30m

Eating Children

plan is still very much being field-tested by me. I’m making the code
available, but chances are, it will eat your children. I’d appreciate it if
bugs were reported to the github issue tracker.

Implementation Overview

And now onto the technical part: the implementation. You may have taken notice
that I’ve referred to plan as a time allocator. This is because time is a
resource that is allocated in a way that is very similar to the way we allocate
memory (a la interfaces such as malloc). We allocate a contiguous block of
time just as we would allocate a contiguous block of memory (we use a best-fit
algorithm to find a block of time that is free, and allocate it). Similarly,
just as the memory allocation process is susceptible to fragmentation, so is
the time allocation process.

Most operating systems textbooks demonstrate the principals of memory
allocation, but they do not indicate that memory allocation is a subset of
resource allocation. If I showed you how a resource allocator worked, you’d say
that it looks very much like a simplistic memory allocator. You’d be right. Any
resource that can be allocated as a block of integers (like process id’s,
device id’s, virtual addresses) could be allocated with a resource allocator.
Today you could implement a malloc interface using a couple dozen invocations
of a resource allocator’s functions and some system calls.

This only goes to show that modern memory allocators are far, far more complex
than the toy allocators found in systems programming texts. Modern allocators
use very advanced concepts like slabs, magazines, and cache-coloring to
maximize performance, and minimize fragmentation. In other words memory
allocation is a special case of resource allocation.

Instead writing a new resource allocator , I’ve decided to make use of the
existing resource allocator that is used as the back-end of libumem called
vmem. I could’ve used any resource allocator (like the ubiquitous rmalloc),
but seeing as how I use libumem for memory allocation anyway, vmem seemed
like the apparent choice.

So as you can probably tell, plan won’t be able to run on any systems that
don’t support, libumem. Fortunately, someone went through the trouble of
porting libumem over to a bunch of platforms.

The other important aspect I have to mention is data-storage. Apparently we
have to save the schedules we make. Most applications would use an on-disk
format, such as a plain-text file, or an embedded database, like SQLite.

Since I use ZFS on all of my machines, a database is automatically a
non-starter, because as they are modified, the data get fragmented. This is not
ZFS’s fault. The databases were designed with 1980’s era filesystems (which
were not COW or resilient) and data (which was rather small, relative to today)
in mind.

Also, databases love to checksum stuff, which is unnecessary as ZFS already
checksums all of the data. There is also a bunch of other overhead and
redundancy associated with databases, which makes them the wrong choice for
this particular problem.

The other option (plain text file) has to be parsed (using lex and yacc if
the format is complex enough).

I love parsing, but I love efficiency even more. Efficiency in both the
clock-cycle sense, and the programmer-productivity sense. In this case, I
decided to settle on a middle ground between text-file and database. In case I
didn’t make it obvious enough, I’m a die-hard unix developer. Unix has this
great thing called a hierarchical file system. It’s great for representing any
kind of hierarchical data. Unix also snagged the nifty concept of extended file
attributes from BeOS. Manipulating directories and extended attributes is very
easy, using system calls. By storing certain properties such as time and
duration in distinct extended attributes, I have a random-access interface to
these values (which are stored in their original binary representation). I
won’t make any claims to the superior time-efficiency of this solution compared
to the other two, but it sure is more convenient, as I didn’t have to roll a
custom parser (and serializer) or write single line of SQL code. Also, since
the data is structured at the filesystem level I didn’t have to use any tree
structures to hold the data efficiently in memory. The most significant
structures I use are an array, strings, an enum, and structures that hold
information about activities and todos.

So, to use plan you need at least libumem and Illumos extended attributes
(which are accessed via my new favourite system call: openat()). And it’s
preferable to have ZFS.

If you think plan would be useful on platforms that don’t meet the above
prerequisites, grab the code and port it.

And that’s the implementation overview. If you want more concrete details have
a look at the code.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s