2012-11-28

Progress in three months


I first met C three months ago. I teach her one digit plus, like 3+4. One digit plus is somewhat OK for her, but, two digits were hard to her.  If I taught slowly, she could do it. However, next week she glanced at the same problem, then she said ``Geht's nicht (Can't be!)' and she immediately gave up. The whole month was like that. I thought, ``I see, she is a tough one.''

I told her every time, ``Mathematics is a language. It is a reflection of human mind. Maybe this doesn't make sense for you, but, it's a language. Which means there is a meaning of all of them. So what does it mean 3+4?'' One day, I used a drawing, the other day, I used a block to explain the numbers and plus. I try to show that we can touch the numbers. However, what she wanted know was the answers of her homework. Once she cried that she needed to fill the homework until tomorrow. I felt sorry a bit, but, I said ``The answer is not important. Your understanding is important.'' One point I know her school demands or expects that Hasenshule helps her homework. I am a useless teacher who doesn't tell the homework answers. But I believe it doesn't matter that something is just written on the paper. I believe it is more important she can understand something. So, I continue to be useless.  She once left my class and asked to help the homework to another teacher.

She has already been in Hasenshule for two years. It seems she is always like that. However, recent two or three weeks, she has changed. Last week, I asked her what is equal to 802-456? She first said, 2 - 6 geht's nicht. But she still looked on the paper. Then she put 1 under the 5, then said 12 - 6 = 6. I thought, it doesn't work. But, I just watched how she continue. It looked like she did:
802 - 456 = 800 + 12 - (450 + 6).     ... (1)
This is not correct, it should be:
802 - 456 = 790 + 12 - (450 + 6).     ... (2)
So, I expected she made a mistake. But actually, she did:
802 - 456 = 800 + 12 - (450 + 6) - 10.  ... (3)
This is correct. I didn't understand what she did, so I asked her how to compute this. It was hard that she first could not explain it to me. But, a few minuted later she explained she computed like (3). I asked, ``What you did is completely correct. By the way, how do you think the method (1)?'' I explained the method (1). Unfortunately, she didn't get it. I saw the method (3)'s advantage. In this problem, when I calculated the 1's position, the 100's position was also changed. But, the method (3) didn't change the 100's position. The method seemed more complicated, but, I realized there was an advantage. She solved the rest of all the problems by her method.

I didn't know this method. I learned a new thing that day, she showed the great progress.

Yesterday, she said ``Geht's nicht'' again to the same problem she solved in the last week. However, now I know she can do it.

2012-11-25

Fast lookup child


L is not a so diligent girl. But she sometimes finishes the exercise very quickly. Although I found she repeatedly mistook the same problem. For example, in one exercise, 4+7 was always 12. I asked what is equal to 4 + 7. She used fingers, took a little while, but she answered correctly at the end. Then I noticed, ``Wait, if she solve the problem with this speed, how she can finish the exercise so quickly?'' So, I sat down next to her and watched how she solved the problem.

Surprise! She doesn't calculate at all. She just looks up the last pages and copies the answers. What I was impressed was she was so fast. She was faster than me to look up the questions. I understood why she made the same mistakes again and again. I learned a new German sentence, ``Bitte nicht angucken!'' This means, ``Don't cheat by looking.'' though it's hard to translate to English.

Her speed of cheating is impressive, this might be her talent. I don't know that I shall discourage her talent(?). That's a tough call for me, but I believe it is better to know to calculate numbers. So, today, I said ``Bitte nicht angucken!'' to her again. But I still don't know. Teaching is a tough business.

2012-11-24

How to disable KDE Wallet Service prompt in Kubuntu 12.04.

To remove the KDE Wallet popup when I logged in in Kubuntu 12.04.
  1. Install the kwalletmanager.  (This is the tricky part, if you deinstall it you can not disable it.)
  2. Open KDE-system settings, Open Account details -- KDE Wallet (If you didn't install it, you don't see the KDE wallet.)
  3. Uncheck Enable the KDE wallet subsystem.
Because the popup is caused by kwalletd, that is kde's base runtime, so you can not remove it as long as you use kde. The deinstalling kwalletmanager only removes its GUI and tools, the subsystem is there. Therefore, deinstall the kwalletmanager doesn't help.
KDE Wallet service popup window which I want to disable
Thanks to Joerg who told me there is a way to disable this.

2012-11-18

Bugs you never want to know about the details: How to call a global static destructor twice.

Abstract

One of my favorite column is ACM's Kode Vicious (e.g., http://doi.acm.org/10.1145/1364782.1364791). I am also a developer, and I am sure that I encounter the bugs that makes his blood pressure high. This bug was ``a global static destructor is called twice.''

Contents

I basically avoid to write a code that has static objects. Because static objects has a side effect and also their construction and destruction order is not under the programmer's control in C++ language. Then, why I encounter this bug? Well, I didn't write it at the first  place. But I can not avoid since it is a part of my job.

I found my crash is caused by a static destructor is called twice. I first thought, the stack is corrupted, since I didn't know it is possible except the compiler bug. In C++, static object constructed and destructed only once, the constructor is called before the main function starts, and the destructor is called after main function finished. The number of call is guaranteed by the compiler.

But, actually it is possible to trick the compiler, depends on how to link the objects. The idea is using dlopen() as the following:

Link a static object A to the application that has main() function.
Create a shared library S which contains the static object A.
The application's main() loads the shared library S dynamically, and unload.

Some may got the idea. The rest is details in my code example.

  • example_factory.h is in the shared library and provides the interface of IExample_class for the application.
  • example_factory_impl.h, example_factory_impl.cpp is the implementation of the interface and in the shared library. There is a static object in here.
  • factory_interface.cpp provides an access point to the shared library.
  • call_static_destructor_twice.cpp is the application that uses the shared library.

These code themselves are not enough to call the static destructor twice. You need the following build script to create the application and the shared library.

Build script

#!/bin/bash -x
#
# How to call the static destructor twice.
# Copyright (C) 2012 Hitoshi
#

# create a shared lib.
LIB_SRC="factory_interface.cpp example_factory_impl.cpp"
LIB_OBJ="factory_interface.o   example_factory_impl.o"

g++ -g -Wall -fPIC -c ${LIB_SRC}
g++ -shared -Wl,-soname,libexample_factory.so -o libexample_factory.so ${LIB_OBJ}

# create an application that dynamically loads the shared lib.
APP_SRC="call_static_destructor_twice.cpp"
APP_OBJ="call_static_destructor_twice.o"

#
# correct build
#
# g++ -g -rdynamic -o test_example ${APP_SRC} -ldl

#
# evil build. The same symbol, but two static objects are constructed
# and destructed. If these objects looks up a system wide global
# resource and delete twice, you have a difficult bug.
#
g++ -g -o test_example ${APP_SRC} -ldl example_factory_impl.o



In the ``evil build,'' we link the object file that contains the static object. This is wrong and this was the bug in our build system. These kind of bug is hard to debug. The execution result is the following. The execution environment is Kubuntu 12.04, g++ 4.6.3. As you see, static object's constructed and destructed twice. In our real bug, this caused a crash on exit.

Execution result

% ./test_example
Example_class::Example_class()
info: loading [./libexample_factory.so]...
Example_class::Example_class()
info: library [./libexample_factory.so] has loaded.
Example_factory::Example_factory()
info: new IExample_class.
Example_class::Example_class()
Example_class::~Example_class(): I am created by new_example_class().
info: unloading [./libexample_factory.so]...
Example_class::~Example_class(): I am static since not changed.
info: library [./libexample_factory.so] has been unloaded.
Example_class::~Example_class(): I am static since not changed.

File: example_factory_h

// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory_h
/// \brief an example interface class.

#ifndef EXAMPLE_FACTORY_H
#define EXAMPLE_FACTORY_H

#include 

//----------------------------------------------------------------------
/// Example class interface. This is created by the IExample_factory.
///
class IExample_class
{
public:
    /// default constructor
    IExample_class()
    {
        // empty. This is needed since app only know this and the
        // constructor can not be pure virtual.
    }
    /// destructor
    virtual ~IExample_class()
    {
        // empty. This is needed since app only know this and the
        // destructor can not be pure virtual.
    };
    /// print out message
    virtual void print() const = 0;

private:
    // members

private:
    /// copy constructor. prohibit until proved useful.
    IExample_class(IExample_class const & rhs);
    /// operator=. prohibit until proved useful.
    IExample_class const & operator=(IExample_class const & rhs);
};

//----------------------------------------------------------------------
/// Example factory interface. The factory of all the shared library
/// objects.
class IExample_factory
{
public:
    /// default constructor
    IExample_factory()
    {
        // empty. This is needed since app only know this and the
        // constructor can not be pure virtual.
    }
    /// destructor
    virtual ~IExample_factory()
    {
        // empty. This is needed since app only know this and the
        // destructor can not be pure virtual.
    }
    /// print out message
    virtual void print() const = 0;

    /// new IExample instance
    virtual IExample_class * new_example_class() = 0;
    /// delete IExample instance
    virtual void delete_example_class(IExample_class * p_iec) = 0;

private:
    /// copy constructor. prohibit until proved useful.
    IExample_factory(IExample_factory const & rhs);
    /// operator=. prohibit until proved useful.
    IExample_factory const & operator=(IExample_factory const & rhs);
};
//----------------------------------------------------------------------
#endif // #ifndef EXAMPLE_FACTORY_H

FILE: example_factory_impl.h

// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory_impl.h
/// \brief an example class. Print a message when destruct.

#include "example_factory.h"
#include 

//----------------------------------------------------------------------
/// Example class implementation.
///
class Example_class : public IExample_class
{
public:
    /// default constructor
    Example_class();
    /// destructor
    virtual ~Example_class();
    /// print out message
    virtual void print() const;
public:
    /// set message
    /// \param[in] mes message for print().
    void set_message(std::string const & mes);
private:
    // message
    std::string m_mes;
private:
    /// copy constructor. prohibit until proved useful.
    Example_class(Example_class const & rhs);
    /// operator=. prohibit until proved useful.
    Example_class const & operator=(Example_class const & rhs);
};
//----------------------------------------------------------------------
/// Example factory implementation. The factory of all the shared
/// library objects.
///
class Example_factory : public IExample_factory
{
public:
    /// default constructor
    Example_factory();
    /// destructor
    virtual ~Example_factory();
    /// print out message
    virtual void print() const;
    /// new Example instance
    virtual IExample_class * new_example_class();
    /// delete Example instance
    virtual void delete_example_class(IExample_class * p_iec);

private:
    /// copy constructor. prohibit until proved useful.
    Example_factory(Example_factory const & rhs);
    /// operator=. prohibit until proved useful.
    Example_factory const & operator=(Example_factory const & rhs);
};
//----------------------------------------------------------------------

FILE: example_factory_impl.cpp

// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file example_factory_impl.cpp
/// \brief an example class. Print a message when destruct.

#include "example_factory_impl.h"

#include 

//----------------------------------------------------------------------
// default constructor
Example_class::Example_class()
    :
    m_mes("I am static since not changed.")
{
    std::cout << "Example_class::Example_class()" << std::endl;
}
//----------------------------------------------------------------------
// destructor
Example_class::~Example_class()
{
    std::cout << "Example_class::~Example_class(): " << m_mes << std::endl;
}
//----------------------------------------------------------------------
// print out message
void Example_class::print() const
{
    std::cout << "Example_class::print(): " << m_mes << std::endl;
}
//----------------------------------------------------------------------
// set message
void Example_class::set_message(std::string const & mes)
{
    m_mes = mes;
}
//======================================================================
// default constructor
Example_factory::Example_factory()
{
    std::cout << "Example_factory::Example_factory()" << std::endl;
}
//----------------------------------------------------------------------
// destructor
Example_factory::~Example_factory()
{
    std::cout << "Example_factory::~Example_factory(): " << std::endl;
}
//----------------------------------------------------------------------
// print out message
void Example_factory::print() const
{
    std::cout << "Example_factory::print() is called." << std::endl;
}
//----------------------------------------------------------------------
// new Example_class
IExample_class * Example_factory::new_example_class()
{
    Example_class * p_iec = new Example_class();
    p_iec->set_message("I am created by new_example_class().");
    return p_iec;
}
//----------------------------------------------------------------------
// create b
void Example_factory::delete_example_class(IExample_class * p_ec)
{
    delete p_ec;
}
//----------------------------------------------------------------------
// Static global object!
Example_class an_example_class;
//----------------------------------------------------------------------

FILE: factory_interface.cpp

// ----------------------------------------------------------------------
// An example class for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
// ----------------------------------------------------------------------
/// \file factory_interface.cpp
/// \brief dynamically loaded class factory

#include "example_factory_impl.h"

//======================================================================
/// singleton for dynamic shared lib object tracking
class Shared_lib_object_tracker
{
public:
    /// get the instance
    /// \return example factory
    static IExample_factory * instance()
    {
        if(G_p_example_factory == 0){
            G_p_example_factory = new Example_factory();
        }
        return G_p_example_factory;
    }
    /// peek the instance
    /// \return example factory, may 0 if not yet accessed.
    static IExample_factory * peek_instance()
    {
        return G_p_example_factory;
    }
    /// delete the singleton.
    static void delete_instance()
    {
        if(G_p_example_factory != 0){
            delete G_p_example_factory;
            G_p_example_factory = 0;
        }
    }
private:
    // singleton instance
    static IExample_factory * G_p_example_factory;
private:
    /// default constructor
    Shared_lib_object_tracker()
    {
        // empty
    }
private:
    /// copy constructor. prohibit until proved useful.
    Shared_lib_object_tracker(Shared_lib_object_tracker const &);
    /// operator=. prohibit until proved useful.
    Shared_lib_object_tracker const & operator=(Shared_lib_object_tracker const &);
};

// singleton instance
IExample_factory * Shared_lib_object_tracker::G_p_example_factory = 0;

//======================================================================
extern "C"
IExample_factory * shared_lib_factory()
{
    if(Shared_lib_object_tracker::peek_instance() != 0){
        std::cerr << "Double call of the shared_lib_factory." << std::endl;
        return 0;
    }
    return Shared_lib_object_tracker::instance();
}
//======================================================================

FILE: call_static_destructor_twice.cpp

//----------------------------------------------------------------------
// An example code for how to call static destructor twice demo.
// Copyright (C) 2012 Hitoshi
//----------------------------------------------------------------------
/// \file call_static_destructor_twice.cpp
/// \brief how to call static destructor twice

#include 
#include 
#include 
#include 

#include "example_factory.h"

// globals for open and close
static void * G_p_handle = 0;
char const * const G_p_lib_name = "./libexample_factory.so";

//----------------------------------------------------------------------
/// load shared library
IExample_factory * load_library()
{
    fprintf(stdout, "info: loading [%s]...\n", G_p_lib_name);
    G_p_handle = dlopen(G_p_lib_name, RTLD_LAZY | RTLD_DEEPBIND);
    if(G_p_handle == 0){
        // iostream seems has some static. Avoid to use it here.
        fprintf(stderr, "error: null handle: %s\n", dlerror());
        return 0;
    }

    void * p_symbol = dlsym(G_p_handle, "shared_lib_factory");
    if (p_symbol == 0) {
        fprintf(stderr, "error: symbol: %s\n", dlerror());
        return NULL;
    }

    typedef IExample_factory* (Factory_func());
    Factory_func * factory = (Factory_func*)p_symbol;

    fprintf(stdout, "info: library [%s] has loaded.\n", G_p_lib_name);

    return factory();
}

//----------------------------------------------------------------------
/// unload shared library
bool unload_library()
{
    fprintf(stdout, "info: unloading [%s]...\n", G_p_lib_name);
    assert(G_p_handle != 0);

    int result = dlclose(G_p_handle);
    if(result != 0){
        fprintf(stderr, "error: unload library: %s\n", dlerror());
    }

    // unload check can only be done by reload with RTLD_NOLOAD, see
    // the manual.
    void* handle = dlopen(G_p_lib_name, RTLD_LAZY | RTLD_NOLOAD | RTLD_DEEPBIND);
    if(handle != 0){
        fprintf(stderr, "error: Failed to unload %s\n", G_p_lib_name);
    }
    else{
        fprintf(stdout, "info: library [%s] has been unloaded.\n", G_p_lib_name);
    }
    return (handle == 0);
}

//----------------------------------------------------------------------
void dynamic_loading()
{
    // load
    IExample_factory * p_factory = load_library();
    fprintf(stdout, "info: new IExample_class.\n");

    IExample_class *p_exp = p_factory->new_example_class();
    // p_exp->print();
    p_factory->delete_example_class(p_exp);

    // unload
    unload_library();
}
//----------------------------------------------------------------------
int main()
{
    dynamic_loading();
    return 0;
}
//----------------------------------------------------------------------

2012-11-04

Authors in a Markov matrix: Which author do people find most inspiring? (7)


The adjacency matrix

A matrix is a two-dimensional rectangular array of numbers arranged in rows and columns. It looks like a table of numbers. The readers who want to more about matrix, see the Appendix A (will be shown up the later blog) in this document as a short introduction, or to know more deeply, see [7].

I would like to show how a matrix can be used to describe a graph. My motivation is to be able to write down a graph. Following some rules, we can write down a graph in matrix form. Let me introduce such a method for representing a graph here. The matrix I will describe is called an adjacency matrix.

Definition: An adjacency matrix \(A\) of a graph of \(N\) vertices is an \(N \times N\) matrix where the element \(a_{i,j}\) is 1 when there is a directed edge from node \(i\) of the graph to node \(j\), otherwise 0.

That's all there is to it. An element in an adjacency matrix that represents a connection is a 1; an element that represents the lack of a connection is a 0.  Let me show you some examples.

First, let's think about how we could represent relationships between people as a graph. A graph edge will represent that one person likes another person. I've decided to have an edge when someone likes someone else. It would be possible for an edge to mean that two people dislike each other, but I would prefer to know more about who likes whom.  A note here, however --- a definition like the one I am making for my graph depends on me, the person who is solving the problem. I can define any meaning for a graph as long as there is no contradiction. This is not based on facts, but on what I have defined, so we first need to agree with this idea.  If I say ``define,'' ``assume,'' or ``let us think...'', I am asking you to agree. If you don't agree with these initial definitions, then the rest of the discussion is meaningless!

Next time I will introduce Alice and draw a like-not-like graph.

References

[7] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition,'' Wellesley-Cambridge Press, 2009