Understanding Memory: Part 1

This article is meant for programmers who have some familiarity with writing and compiling simple code in C/C++. It assumes the reader knows basic data types like int and double and how to define and use variables and functions. This article will then expose the reader to a basic memory model, explain how the use of variables interacts with this memory, and introduce addresses and pointers.

On a modern platform, memory is presented to a program as byte-addressable blocks. Each byte in this block has an associated integer address; this address is used to identify to the computer which piece of memory to operate on. For this demonstration, let us assume our program has a block of memory with the first byte at address 0×10. Each variable we declare in our program must occupy some of this memory. The compiler we’re using will use this memory to store variables we define. Different data types can be different sizes: an int type is commonly 4 bytes, while a double is usually 8.

int cakes = 10; // 4 bytes starting at 0x10.
double level = 11.5; // 8 bytes starting at 0x14.

To manipulate these variables, we simply assign a value to their symbols, since their addresses have been managed for us by the compiler:

cakes = 15; // the compiler knows where "cakes" is stored in memory

Addresses and Pointers

Now, we would like to modify the values of these variables from an external function. This function does not know about the variables we have declared here because it exists at a different scope. We need two things to accomplish this. First, we need a way to obtain the address of our cakes variable in memory. For this, we can use the address of operator, &. Second, we need a variable into which this address can be stored; this is the pointer type, specified by a data type and a *. The size of the pointer type on this platform is 8 bytes, allowing for a 64-bit address space.

int *pointer_to_cakes; // 8 bytes starting at 0x18.
pointer_to_cakes = &cakes; // the value of pointer_to_cakes is 0x10

To modify the value through the pointer, we dereference, using the * operator.

*pointer_to_cakes = 25; // cakes is now 25

Lets go ahead and modify this value in our function.

/* Function takes a pointer to an int, allowing it to modify the value */
void get_num_cakes(int* how_many_cakes) {
    *how_many_cakes = 17;
}

get_num_cakes(pointer_to_cakes); // sets cakes to 17.
get_num_cakes(&cakes); // can pass address directly.

The next extension to this happens when we would like someone to modify the value of pointer_to_cakes, so that its value contains a different address. The principle of course is the same: to modify a variable, one must know its address.

void set_cake_ptr(int** cake_ptr_ptr, int* new_cake_ptr) {
    *cake_ptr_ptr = new_cake_ptr;
}

int another_cake = 1; // 4 bytes at 0x1C
set_cake_ptr(&pointer_to_cakes, &another_cake); // pointer_to_cakes is now 0x1C

Posted in Software | Tagged , | Leave a comment

Enable WordPress Automatic Updates on a Debian Server

I attempted to get WordPress to update plugins automatically on my Debian server today, and found it a bit less than trivial due to the number of configuration gotchas.

Assuming you’re running a Debian server (I have 6.0 Squeeze), on which WordPress is installed in /var/www/site/public_html:

1) Install required packages. I used vsftpd.

sudo apt-get install vsftpd openssl

2) Configure vsftpd. I set the following options in /etc/vsftpd.conf

# Enable only local users, no anonymous
anonymous_enable=NO
local_enable=YES
write_enable=YES
local_umask=022

# Allow only our special FTP user
userlist_enable=YES
userlist_deny=NO
userlist_file=/etc/vsftpd.allow_list

# Here's the security trick -- listen only on the local interface to 
# prevent external connections
listen_address=127.0.0.1

# Enable debugging until everything works :)
log_ftp_protocol=YES

3) Add a user for ftp access

# Add the user
sudo useradd ftpsecure -d /var/www

# Set a password. Since vsftpd is only listening on localhost, the 
# security of this password isn't too important.
sudo passwd ftpsecure

# Add to the vsftpd allow list
echo "ftpsecure" | sudo tee -a /etc/vsftpd.allow_list

4) Turn on vsftpd:

sudo /etc/init.d/vsftpd restart

5) Set permissions for ftpsecure to access your wordpress files. I use access control lists (ACLs), but you could use chown/chmod if you want. These may seem like a bit to permissive — keep in mind that the only way ftpsecure can log in is from your server.

setfacl -m u:ftpsecure:r-x /var/www/site/

# The updater needs access to the root site
setfacl -R -m u:ftpsecure:rwx /var/www/site/public_html
setfacl -R -d -m u:ftpsecure:rwx /var/www/site/public_html

7) Tell WordPress about your FTP credentials. In /var/www/site/public-html/wp-config.php:

define('FTP_HOST', 'localhost');
define('FTP_USER', 'ftpsecure');
define('FTP_PASS', '<password>');

6) Run an update. If WordPress asks for the connection type, choose FTP. Try getting WordPress to update a plugin or the entire site. If it fails, view the log with

tail -f /var/log/vsftpd.log

and run the update again. You’ll be able to tell from the log if there was a permission problem.

7) Disable logging. Remove the line

log_ftp_protocol=YES

in /etc/vsftpd.conf

8) You’re done!

Comment below if these steps didn’t work for you.

For reference, I used:

Posted in Software | Tagged , | 6 Comments

When you need std::remove_const

I ran across an interesting case where I needed to use std::remove_const to ensure a template parameter wasn’t const by default. I had something like this:

const Matrix<4> m4 = Identity;
Vector<3> v3 = project(m4[3]);

With the library I was using, TooN 2.0.0 beta8, this resulted in a compile error. The error stated that when the vector returned from project() was being created, the compiler couldn’t invoke assign to a read only location. A simplified declaration of project() looks as follows:

template <int Size, typename Precision, typename Base>
Vector<Size-1,Precision> project(const Vector<Size, Precision, Base>& v);

What the project() function returns is not important; what is important is the use of the template parameter Precision in both the argument type and the return type. When I invoke operator[] on a const Matrix object, the returned vector’s precision inherits the const.

template <int Rows, int Cols, class Precision>
class Matrix {
...
Vector<Cols, const Precision, Slice> Matrix::operator[](int row) const;
};

When this vector is passed to the project() function above, the function tries to create and return a Vector<3, const double> which can only be initialized with a constexpr. Assigning to it via operator= or a constructor will not work to copy the data from the other vector.

There are several ways one can fix this, all of them involving removing the const qualifier from the Precision type on the returned vector.

It may seem like a simple solution would work:

template <int Size, typename Precision, typename Base, typename P2>
Vector<Size-1, P2> project(const Vector<Size, Precision, Base>& v);

Unfortunately, this requires the function be invoked as project<Size, Precision, Base, P2>(v); which is undesirable.

Solution #1

The first solution is simple, but tedious if you have several functions with similar signatures:

template <int Size, typename Precision, typename Base>
Vector<Size-1, typename std::remove_const<Precision>::type > 
project(const Vector<Size, Precision, Base>& v);

std::remove_const<T>::type is a type expression equal to the original type T, but with any const qualifiers removed. In this way, const double becomes simply double.

Solution #2

Another solution is to prevent the creation of a Vector object with a const precision, the idea that a non-slice vector with const data isn’t very useful — you can’t even construct one properly. Generally the only time you would actually want a vector with const data is when that data is pointing to some already existing area in memory (a slice).

Consider the following toy code for a vector class:

#define DECLARE_TYPES(T) \
    typedef typename std::remove_const<T>::type PlainType; \
    typedef const T ConstPlainType; \
    typedef typename std::remove_const<T>::type& ReferenceType; \
    typedef const T& ConstReferenceType

struct StackBase {
template <int Size, typename P>
class Layout { 
public:
    DECLARE_TYPES(P);
    PlainType data[Size];
};
};

struct SliceBase {
template <int Size, typename P>
class Layout {
public:
    P* data;
};
};

template <int Size, typename P = double, typename B = StackBase >
class Vector : public B::template Layout<Size, P> {
public:
    DECLARE_TYPES(P);
    using B::template Layout<Size, P>::data;

    ConstReferenceType operator[](int i) const { return data[i]; }
    ReferenceType operator[](int i) { return data[i]; }
};

When the Vector object is backed by owned storage (StackBase), the data is declared explicitly to be of a non-const type. Similarly, the return types of operator[] are defined to be the const and non-const reference types. The SliceBase, which handles references to un-owned data, retains the original templated type to allow pointing to constant data.

While this method prevents the creation of Vector objects with const owned data, it also means you don’t have to augment functions that interface with these objects to correct the return type.

Posted in Software | Tagged , | Leave a comment

Correcting Message Order with Courier

Recently I moved some local messages from my machine (previously downloaded with pop3) onto the server so I could use imap. I used Mail.app on Mac OS X 10.5.8 to do this.

For some reason, the messages in this example were uploaded in a way that caused them to be loaded in the wrong order on iOS 5.0.1. Since I run the mailserver myself, I took a look at the message files to see if I could deduce the cause of the issue. I noticed a series of messages on the mail server that looked like this:

1324697191.M91227P15574V000000000000CA00I0004B07D_556.hostname,S=5622:2,S
1324697192.M322096P15574V000000000000CA00I0004B07F_557.hostname,S=225691:2,RS
1324697196.M144018P15574V000000000000CA00I0004B081_558.hostname,S=7702:2,RS
1324697197.M715598P15574V000000000000CA00I0004B083_559.hostname,S=15741:2,S
1324697199.M327587P15574V000000000000CA00I0004B085_560.hostname,S=8744:2,RS

The received times of these messages, in the same order as listed above, are:

01/15/2010
01/09/2009
07/13/2010
02/21/2010
05/06/2010

It turns out that due to the messages in this example having a modification date that doesn’t match their receive timestamp the messages appear in the wrong order on an iOS device, where the mail application assumes the order of the messages it gets from the imap server is already sorted by date. This isn’t a problem with desktop mail clients — they simply fetch all the messages, sort them, and everything is fine. Several google searches on this subject yielded threads where people were trying to get their messages in the correct order and the suggested remedy was “sort them on the client side.”

To fix this, I wrote a perl script script to read the message headers, determine the receive time, and update the file name and modification date to match.

Use the script like this:

perl rename.pl cur/*

When you’re convinced it will do the right thing:

perl rename.pl cur/* --output-dir cur_renamed

After ensuring the rename was correct, I swapped the cur and cur_renamed directories, deleted the courierimapuiddb file, and restarted courier-imap. I also had to quit Mail.app on OS X and delete and re-add the mail account on the iOS device to get the messages to come in in the correct order.

Posted in General | Tagged , , | Leave a comment

Google Authenticator Backup Woes

TL;DR: Google Authenticator doesn’t backup on iOS; before erasing your old device, make sure to re-configure Google Authenticator on your new one.

I use the Google Authenticator app on iOS for 2-factor authentication into Google’s services. Recently, I was transitioning to a new phone after giving my existing one to my mom for Christmas. I did the standard backup -> restore plan which put most of my settings on my new device without issues. Fortunately, before I erased the old device, I made sure all my apps worked, including the authenticator.

Apparently, the data the authenticator app stores is not backed up for whatever reason, which means that instead of being able to generate the keys needed to access my accounts, the authenticator was prompting me to set up a new account. The smart folks over here recommend taking a screenshot of the QR code Google’s site gives you when you set up 2-factor authentication.

Questions:

To Google: Why doesn’t the authenticator back up its data? Seems this could be a nasty surprise for someone.
To Android users: Does this happen on Android as well?

Posted in General | Tagged , | 1 Comment

Cubic Spline Interpolation

Cubic spline interpolation is a simple way to obtain a smooth curve from a set of discrete points (knots). It has both C1 (first derivative) and C2 (second derivative) continuity, enabling it to produce a continuous piecewise function given a set of data points.

From the algorithm detailed here I have implemented a clamped cubic spline class in C++. It is templated on the type of X and Y, allowing for use of scalar or vector types. It requires only that X and Y define the operators +, -, *, and /, and that Y have a constructor that takes a single scalar argument, initializing all elements to the supplied value.

Usage is very simple. For example, to interpolate a 2D location over time, try this:

#import "glm.hpp"
#import <vector>

std::vector<float> times;
std::vector<glm::vec2> points;
times.push_back(0);
points.push_back(glm::vec2(0));
times.push_back(.5f);
points.push_back(glm::vec2(-303, -572));
times.push_back(1);
points.push_back(glm::vec2(-250, -980));

/* Create the spline interpolating the position over time */
Spline<float, glm::vec2> sp(times, points);

/* Compute the interpolated position at time 0.75f */
glm::vec2 value(sp[.75f]);

The code for the spline class is below:

Continue reading

Posted in Computer Vision, Software | Tagged , , , , | 6 Comments

Houses in Minecraft

So I’ve been playing Minecraft, focusing mainly on the creative aspect, although I play the new Beta client and run my own server locally so I get the features added post-classic. I’ve turned off monster spawning and set the difficulty to Peaceful, so I can focus on bringing creations to life instead of running from scary monsters in the night.

The first time I played with monsters, I found the sound of a zombie’s “murrrrrrrr” in a dark, endless cavern to be frightening enough that I never wanted to hear it again. /shivers.

I find the first-person building experience to be very satisfying to the OCD urge within me that wants to make everything right. As all blocks are destroyable (with the exception of Bedrock), any reality can be created given enough time. I’m fond of using the different kinds of blocks to vary the aesthetics — even if the blocks type is not practical.

My favorite activity is to visualize my buildings at night, as I find the lighting of torches, lava, and glowstone to create a very pleasing effect. I also make frequent use of glass to provide a sense of openness and to allow light to mix between areas.

Here’s some screenshots of a large house on top of a hill that I’ve been working on.

The master bedroom

The spacious master bedroom.

Continue reading

Posted in General | Tagged , , | 2 Comments

Time Machine Exclusions – Snow Leopard

A bit late, but here’s an update of the Time Machine exclusion list for Snow Leopard. Continue reading

Posted in Software | Tagged , | Leave a comment

NSCopying and Mutability

In the Cocoa frameworks, it is common to find mutable and immutable versions of classes that store data, such as strings, dictionaries, and arrays. Most of these classes also implement the NSCopying informal protocol, and those with mutable varients implement the NSMutableCopying protocol. These protocols specify methods for obtaining immutable and mutable copies of an object. These copying methods should be implemented such that the copy can return an instance of a subclass, to allow for subclasses to copy their specific instance variables.

There are situations, however, that can result in the inability of a subclass to do so. Consider NSURLRequest:

@interface NSURLRequest : NSObject &lt;NSCoding, NSCopying, NSMutableCopying&gt;

An immutable class, but one that implements NSMutableCopying, it responds directly to the -mutableCopyWithZone:(NSZone *)zone method that returns a mutable url request, an instance of NSMutableURLRequest. While this isn’t a problem in itself, it becomes an issue when this method is not re-implemented in NSMutableURLRequest.

– Nope: Implement the NSMutableCopying protocol only in your immutable class.

The implementation of -mutableCopyWithZone:(NSZone *)zone in the immutable class must certainly hard-code the name of the mutable class — it cannot be aware of any external subclasses of the mutable class. This means that asking for a mutable copy of the immutable class creates an instance of the known mutable subclass. Consider the following example:

@interface MyMutableURLRequest : NSMutableURLRequest {} @end

MyMutableURLRequest *request = [MyMutableURLRequest requestWithURL:url];
request = [request mutableCopy];

In this case, the object returned from -mutableCopy will be an instance of NSMutableURLRequest instead of the expected MyMutableURLRequest.

– Nope: Hardcode class names in -copyWithZone: and -mutableCopyWithZone:

Hardcoding class names serves to block subclassers from subclassing the copy methods without dirty hacks.

+ Yup: [Re]Implement the NSMutableCopying protocol in your mutable class.

By doing this, the class name doesn’t have to be hard-coded (in the mutable class), and so a subclasser can simply call [super mutableCopy] and then copy their specific instance variables.

+ Yup: Use [self class] in -copyWithZone: and -mutableCopyWithZone:

By using [self class], an object of the subclass type will be allocated.

Posted in Software | Tagged , , , | 1 Comment

Readable If Statements

To kick of the Coding Yups and Nopes section, I’ll start with something simple. There are a set of things to do, and a set of things to avoid. For each thing, there are one or more reasons justifying its classification. These reasons are ordered by descending importance and increasing subjectivity.

– Nope:

if (condition) doWork();
else doOtherWork();

  • If you’re stepping through with a debugger (I used gdb), it is difficult to tell when stepping over the line if the statement is executed. To do so you must determine the value of condition, or determine if the function was called based on its side effects.
  • If you add an additional statement to the false case, it’s possible that braces may be forgotten, leading to incorrect operation.
  • Assuming the reason for putting both condition and statement on one line was to use less lines, the benefits of this are negated by the decreased readability of such a statement. By putting both condition and statement on one line, searching for a specific condition becomes more difficult.
  • Assuming other parts of your code are scoped and indented, this breaks that pattern.

if (condition) {
    doWork();
} else doOtherWork();

  • Similar to the above case. Basically this is inconsistent and has none of the advantages of either method.

if(condition){
    doWork();
}

  • This is a pure spacing issue. if is not a function, please do not call it as one. Also, that brace is squashed against that parentheses, give it some room! Skimping on spacing issues like this while writing makes it harder to read later.

+ Yup:

if (condition) {
    doWork();
} else {
    doOtherWork();
}

  • The perfect if-else statement. Well spaced, condition and statement on separate lines.

if (error) return;
if (error) break;
if (error) continue;

  • When used only for error/early exit conditions, these help to condense code so that the reader can quickly get to the meat of a function.
  • The statements and the condition are on one line because I do not consider the flow control statements return, break, and continue to contribute useful work, such that it should be scoped in braces and on its own line.
Posted in Software | Tagged , , , , | Leave a comment