Mt: C language for heavily loaded servers

Greetings, Khabrovites!

I want to offer ideas for discussion on how to simplify the writing of server programs in C by introducing additional language tools. I believe that this topic may be of interest to all developers who have had to deal with writing multithreaded or asynchronous code.

At the moment, I have almost completed writing a toolkit - a parser generator, a C parser and partially C ++ - which allows you to start writing a translator that supports language extensions, which I will talk about here. But before continuing, I would like to consult with colleagues in the workshop and find like-minded people.

We will talk about multi-threaded asynchronous servers. Asynchronous - that is, using event-based customer-service logic (epoll / kqueue), in which multiple clients are served by one thread at a time. Multi-threaded - means ready to take advantage of modern multi-core processors, performing parallel maintenance of connections by multiple threads within the same process.

Asynchronous service model allows you to create servers that are most prepared to work with a really high load. But asynchronous (non-blocking) code is more difficult to write than synchronous, blocking code. In addition, it is much more difficult to write asynchronous multi-threaded code: it is too easy to make mistakes when synchronizing access to shared data, and it is too difficult to detect such errors. This leads to the fact that in practice it is often wiser to completely refuse to support multithreading.

Having gained some experience in writing such programs, I began to notice that the solution to the main problems of thread synchronization is solved by standard methods, the use of which could be automated at the language level, significantly simplifying the task for the developer. Then I saw that using a similar approach, you can simplify writing asynchronous event processing code. It is because of the apparent generality of solutions that I propose a single set of language additions for these non-directly related tasks.

The ideas are quite simple, so in order not to create a feeling of complexity, I will list the main points on the additions to C. I will call these additions the “Mt language”.

So Mt is:
  • Automatic mutex control to synchronize access to objects;
  • Asynchronous processing chains, written as regular sequential functions;
  • Annotation - an additional description of program elements for static analysis of source texts;
  • Built-in link counting mechanism;
  • Borrowing the most useful features from C ++;
  • C compatible, tight binding to C ABI. The initial implementation is a translator from Mt to C.
Let me explain why C, and not C ++, was chosen as the base. The main reason is the significantly higher complexity of C ++ in terms of semantic analysis of source texts. Over the past year, I have attempted to write a C ++ parser and a static analysis system for C ++ code. The result - a C parser and parsing C-style semantics were pretty easy, but C ++ parsing is far from complete: the amount of work is too large. Therefore, I decided that good practical results can be achieved by relying on pure C and supplementing it with those C ++ features that are quite simple to implement.

Next, I’ll talk about each addition in more detail. I give some examples of code in C ++, because it is easier to correlate them with the equivalent code in Mt.

1. Automatic Mutex Control


Consider a common request processing scheme. Suppose we have some object of the MyFrontend class, which is an implementation of our server. After receiving and decoding the request from the client, we call the method of the server object processRequest (). This method performs some operations that cause a change in the internal state of the server. For example, suppose that as a result of processing a request, the counter for the number of requests num_requests increases: Mt eliminates the need for manual synchronization: async object declares a class of objects that are safe from the point of view of multithreading. Such objects will be called asynchronous. The given Mt code example is translated into code equivalent to the C ++ example.

    class MyFrontend
    {
    private:
        Mutex state_mutex;
        unsigned num_requests;

    public:
        void processRequest ()
        {
            state_mutex.lock ();
            ++ num_requests;
            state_mutex.unlock ();
        }
    };




    async object MyFrontend
    {
    private:
        unsigned num_requests;

    public:
        async void processRequest ()
        {
            ++ num_requests;
        }
    };




Now suppose that to process the request, MyFrontend should call the doSomething () method of the MyBackend object, passing it the num_back backend access counter as a parameter. In addition, we do not want to think about the possibility of deadlocks and want everything to work with non-recursive mutexes. To do this, we need to free state_mutex before accessing MyBackend: Same thing on Mt: The Mt translator inserts operations with state_mutex on its own and enters a temporary variable to pass the parameter. The call operator was introduced in order to emphasize that for the time the asynchronous method of another object is called, we release the state_mutex lock. In addition, this allows us to explicitly prohibit calling asynchronous methods in expressions.

    class MyFrontend
    {
    private:
        Mutex state_mutex;
        unsigned num_requests;
        unsigned num_back;
        MyBackend *backend;

    public:
        void processRequest ()
        {
            state_mutex.lock ();
            ++ num_back;
            unsigned tmp_num_back = tmp_num_back;
            state_mutex.unlock ();

            backend->doSomething (tmp_num_back);

            state_mutex.lock ();
            ++ num_requests;
            state_mutex.unlock ();
        }
    };




    async object MyFrontend
    {
    private:
        unsigned num_requests;
        unsigned num_back;
        MyBackend *backend;

    public:
        async void processRequest ()
        {
            call backend->doSomething (++ num_back);
            ++ num_requests;
        }
    };




In addition to the above examples, a number of other cases of using locks are automated: waiting for events (events are usually used in conjunction with a mutex that protects the condition for waiting to end), calling an asynchronous method of an object from another method of the same object.

Thus, we minimize the risk of making mistakes when managing a simple lock on the state of an object. According to my observations, if synchronization of access to an object is carried out using not one, but several locks, then most likely there is an unsuccessful design: you should either divide the object into several independent objects, or merge the locks into one. Therefore, by automating the simplest case with one mutex, we solve most of the synchronization problems. The ability to synchronize manually and using other primitives is
preserved.

2. Asynchronous processing chains


In my opinion, this is the most interesting and unusual idea. I will explain with an example illustrating the operation of a real service.

Let's say our server is the front end of the photo hosting. We want to realize the return to customers of HTML-pages with photos of users. The page displays information from the profile of the owner of the photo and the photo itself. Photos can only be viewed by friends of photo owners. Thus, in order to respond to an HTTP request, you need to collect the necessary information by polling a number of internal services.

Request Processing Algorithm:
  1. Send the cookie cookie to the authentication server to identify the user (check_auth);
  2. After checking the authorization, send a request to the server serving the social graph to check whether users are friends (check_friends);
  3. Send a request to the photo owner to the personal data repository (get_userinfo);
  4. After receiving answers from check_friends and get_userinfo, generate an HTML page and send it to the client.
Operation 2 can be performed only after receiving a response to request 1. Request 3 does not depend on requests 1 and 2 and we want it to be executed in parallel with them.

Let's sketch the implementation in C. You can’t get a grasp of this example. Its task is to show how cumbersome the manual implementation of even such a simple asynchronous processing chain is: The resulting code is complex, it is difficult to read. Most of the time when writing it was spent on routine maintenance of the necessary order of operations. Equivalent implementation on Mt: Please note that we are almost completely freed from the routine work of organizing the desired execution order. In addition, the generated C code can be used in multi-threaded programs.

    // Структура состояния асинхронной цепочки.
    typedef struct {
        // "Родительский" класс, управляющий счётчиком ссылок.
        MReferenced parent_referenced;
        // Блокировка на доступ к элементам состояния.
        MMutex state_mutex;

        uint64_t owner_id;
        uint32_t photo_id;

        // Если 'true', то прерываем цепочку.
        bool cancel;

        // Получили ответ от get_userinfo?
        bool got_userinfo;
        // Карма владельца фото (анкетные данные).
        uint32_t owner_carma;

        // Получили ответ от check_friends?
        bool got_friends;
    } HttpPhotoData;

    static void http_photo_data_init (HttpPhotoData *data)
    {
        m_referenced_init ((MReferenced*) data);
        m_mutex_init (&data->state_mutex);

        data->cancel = false;
        data->got_userinfo = false;
        data->got_friends = false;
    }

    static void http_photo__get_userinfo_ret (uin32_t owner_carma,
                                              void *_data);

    static void http_photo__check_auth_ret (uint64_t client_id,
                                            void *_data);

    static void http_photo__end (HttpPhotoData *data);

    // Точка входа в асинхронную цепочку.
    void http_photo (char *cookie_str,
                     uint64_t owner_id,
                     uint32_t photo_id)
    {
        HttpPhotoData *data = m_malloc (sizeof (HttpPhotoData));
        http_photo_data_init (data);

        data->owner_id = owner_id;
        data->photo_id = photo_id;

        {
            m_referenced_ref ((MReferenced*) data);

            MCallbackDesc cb;
            m_callback_desc_init_refdata (&cb, http_photod__get_userinfo_ret, data);

            get_userinfo (&cb, owner_id);
        }

        {
            m_referenced_ref ((MReferenced*) data);

            MCallbackDesc cb;
            m_callback_desc_init_refdata (&cb, http_photod__check_auth_ret, data);

            check_auth (&cb, cookie_str);
        }

        m_referenced_unref ((MReferenced*) data);
    }

    // Ответ от get_userinfo.
    static void http_photo__get_userinfo_ret (uint32_t owner_carma,
                                              void *_data)
    {
        HttpPhotoData *data = (HttpPhotoData*) _data;

        m_mutex_lock (&data->state_mutex);

        if (data->cancel) {
            m_mutex_unlock (&data->state_mutex);
            return;
        }

        data->owner_carma = owner_carma;
        data->got_userinfo = true;

        if (data->got_friends) {
            // Все данные для ответа собраны, отвечаем клиенту.
            http_photo_end (data);
        }

        m_mutex_unlock (&data->state_mutex);
    }

    // Ответ от check_auth.
    static void http_photo__check_auth_ret (uint64_t client_id,
                                            void *_data)
    {
        HttpPhotoData *data = (HttpPhotoData*) _data;

        m_referenced_ref ((MReferenced*) data);

        MCallbackDesc cb;
        m_callback_desc_init_refdata (&cb, http_photo__check_friends_ret, data);

        check_friends (&cb, client_id, data->owner_id);
    }

    // Ответ от check_friends.
    static void http_photo__check_friends_ret (bool friends,
                                               void *_data)
    {
        HttpPhotoData *data = (HttpPhotoData*) _data;

        m_mutex_lock (&data->state_mutex);
        if (data->cancel) {
            m_mutex_unlock (&data->state_mutex);
            return;
        }

        data->got_friends = true;

        if (!friends) {
            // Отказано в доступе. Прерываем цепочку.
            data->cancel = true;
            m_mutex_unlock (&data->state_mutex);
            return;
        }

        if (data->got_userinfo) {
            // Все данные для ответа собраны, отвечаем клиенту.
            http_photo_end (data);
        }

        m_mutex_unlock (data->state_mutex);
    }

    // Отправка ответа клиенту.
    static void http_photo_end (HttpPhotoData *data)
    {
        photo_send_page (data->owner_id, data->photo_id, data->owner_carma);
    }






    async chain void http_photo (char *cookie_str,
                                 uint64_t owner_id,
                                 uint32_t photo_id)
    {
        async call GetUserinfoCall get_userinfo (owner_id);

        async call check_auth (cookie);
            gives uint64_t client_id;

        async call check_friends (client_id, owner_id)
            gives bool friends;

        if (!friends) {
          // Доступ запрещён
            return;
        }

        GetUserinfoCall gives uint32_t owner_carma;

        // Отправляем HTTP-ответ со страницей фото.
        photo_send_page (owner_id, photo_id, owner_carma);
    }




In the above example, two new operators are used:
  • The async call statement describes an asynchronous call. Functions that can be used with this operator must have a special signature: the first parameter is callback, which will be called when the call ends. A callback termination must necessarily be called on any outcome, whether it was a successful call, an internal error, or a timeout.
  • The gives statement sets the point at which to wait for the completion of the specified asynchronous call. gives introduces into the scope the list of values ​​returned by the call. If the async call and give statements must be spaced, then in the async call the call is named and the name of the call is indicated in the give (see GetUserinfoCall in the above example).
In addition to the operators shown, it is possible to process the results of asynchronous calls early so that you can interrupt the chain if an error occurs before we get to the corresponding failed operator call gives. You can also specify an additional destructor for the data included in the state structure of the chain.

The main work that Mt does when translating asynchronous chains in C is as follows:
  • Defines a set of variables to be stored in the chain state structure (HttpPhotoData);
  • Splits the function into smaller ones. Break points are async call statements;
  • It provides the necessary execution order by converting C statements that are violated by the async call and gives statements into equivalent asynchronous constructions according to fixed rules.
It can be shown that each of these operations lends itself well to automation.

The parallel execution of complex chains of operations that cannot be represented by a single function in Mt can be implemented using several different asynchronous chains. That is, if the branches in the chain are so complex that they cannot be described by a single function, then you can construct a description as a composition of several functions.

With the help of Mt, we can describe loops and conditional jumps, broken by waiting for answers from asynchronous calls, in the same simple and familiar form as when writing regular code. Suppose we want to look up a value in three independent caches one after the other : Thus, for asynchronous processing chains, Mt can provide a qualitative leap in expressiveness and usability compared to C.

    async chain void search (int key)
    {
        for (int i = 0; i < 3; i++) {
            async call search_cache (key, i /* cache id */)
                gives int value;

            if (value > 0) {
                printf ("VALUE: %d\n", value);
                break;
            }
        }
    }




3. Annotation


Annotation is an introduction to the code of additional supporting information using annotating words. Annotating words can stand wherever const and volatile qualifiers can stand. All annotating words begin with the '$' character. Examples: The Mt translator is also the basis for a static code verification system that uses annotation for additional checks.
    int * $nonnull ptr;     // указатель не может быть равен NULL
    MyObject * $heap myobj; // объект должен быть выделен с помощью аллокатора




4. Borrowing C ++ Features


From the point of view of translator implementation, the most complex feature of C ++ compared to C is the dependence of the semantic meaning of language constructs on the data types of the arguments. This concerns, first of all, the rules for overloading function names (including operator overloading) and the rules for choosing templates, taking into account partial specializations. Such a dependence means that in order to determine which function or template is used in the infusion, you need to derive the data types of all the arguments to the function or template. This, in turn, requires a complete and accurate implementation of type conversion rules. All this makes up a fairly significant amount of work.

At the same time, name overloading is a controversial property of the language. For example, the creators of the Go language refused it, as there is a meaningful entry in the FAQ .

Mt will not overload function names and operator overloads, multiple inheritance, exceptions, RTTI. Templates without partial specialization are not so difficult to implement, and this is enough to create generalized container classes, so it makes sense to include templates in the language. In the absence of name overloading, templates will become a much simpler and more concise tool: there will be no such metaprogramming capabilities as in C ++.

5. Links and weak links


The absence of operator overloading makes it impossible to implement convenient analogs of “smart pointers” in Mt, such as std :: auto_ptr and boost :: shared_ptr. Instead, a link counting mechanism is proposed at the language level: The basic version uses a simple link counting. Reference counters are built into every synchronous or asynchronous Mt object (object and async object). With this approach to link management, the programmer should avoid creating circular links that lead to a memory leak. Weak links are used to break loops. In the future, you can consider the possibility of using a more complex garbage collector, but now I do not see the need for this. In the absence of operator overloading, there is no need to support C ++ links (of the form int & a) in Mt.
    int  @a; // ссылка
    int @@b; // слабая ссылка







I note that the implementation of links at the language level allows you to get a more complete and convenient mechanism than can be built on C ++ templates.

Conclusion


I have outlined the main features that I intend to include in the Mt. In addition to them, there are other ideas in the development aimed at simplifying the development and reducing the expected number of errors in the programs.

Mt language translator is an open source project. Currently, it exists as a subset of the C ++ language parser and lives in the svn repository mync.svn.sourceforge.net/svnroot/mync/trunk under the working name "scruffy".

If you have thoughts and ideas on adding or changing certain properties of C / C ++ languages, then I suggest voicing them: perhaps the time has come for their practical testing.

I invite you to participate in the project. If you are looking for a topic for independent work, which could give new knowledge and experience, and if successful turn into a high-quality and successful product, then a new language compiler can be an excellent choice. If the problems that Mt is aimed at are not very relevant for you, then you may be interested in developing a C ++ parser and a system for static analysis of C / C ++ programs.

Together we can do more!

Thank you for attention.

Also popular now: