Почему мы используем битовые операторы & и ~ вместо математических операторов% при реализации выровненного mallo c? - PullRequest
Новая
       83

Почему мы используем битовые операторы & и ~ вместо математических операторов% при реализации выровненного mallo c?

2 голосов
/ 01 мая 2020

При изучении управления памятью операционной системы Linux я вижу, что общим решением для реализации выровненной функции mallo c является следующий код: 

void *aligned_malloc(size_t required_bytes, size_t alignment) {
    void *p1; // original block
    void **p2; // aligned block
    int offset = alignment - 1 + sizeof(void *);
    if ((p1 = (void *)malloc(required_bytes + offset)) == NULL) {
       return NULL;
    }
    p2 = (void **)(((size_t)(p1) + offset) & ~(alignment - 1));
    p2[-1] = p1;
    return p2;
}

Это решение имеет проблему то есть он работает правильно только тогда, когда alignment является степенью 2 из-за & ~(alignment - 1). Кроме того, alignment должен быть типом данных size_t, чтобы он соответствовал типу данных указателя p1. Из-за этих ограничений я подумал о другом решении: 

void *aligned_malloc(size_t required_bytes, size_t alignment) {
    void *p1; // original block
    void **p2; // aligned block
    int offset = alignment - 1 + sizeof(void *);
    if ((p1 = (void*)malloc(required_bytes + offset)) == NULL) {
        return NULL;
    }
    offset = (size_t)(p1) % alignment; // offset is used so that I don't have to declare another variable
    p2 = (void **)((size_t)(p1) + (alignment - offset));
    p2[-1] = p1;
    return p2;
}

Это решение решает обе проблемы, то есть alignment не должно быть ни степенью 2, ни size_t тип данных. Мой вопрос заключается в том, почему не используется этот способ реализации выровненного mallo c? Каковы его недостатки, которые заставляют людей выбирать решение с помощью побитовых операторов & и ~ вместо?

Любая помощь действительно приветствуется. Спасибо.

Ответы [ 2 ]

4 голосов
/ 01 мая 2020

Я согласен с вами, что код classi c имеет проблемы, но не совсем те, о которых говорилось:

  • alignment действительно должно быть степенью 2, что является ограничением для стандартной функции POSIX aligned_alloc. На самом деле alignment должно быть степенью 2 больше или равно sizeof(size_t), а аргумент размера должен быть кратным alignment в соответствии с этим стандартом.

  • alignment определяется с типом size_t, но это не связано с типом данных указателя p1. На самом деле, size_t и void * могут иметь различный размер, как это было в случае 16-битной MSDOS / Windows средней и большой модельных архитектур.

    Следовательно, код p2 = (void **)(((size_t)(p1) + offset) & ~(alignment - 1)); не совсем соответствует. Чтобы решить эту проблему, можно использовать uintptr_t, определенный в <stdint.h>, который указан с тем же размером, что и void *: 

    p2 = (void **)(void *)(((uintptr_t)(p1) + offset) & ~(alignment - 1));

  • , есть другая проблема в отправленный код: если alignment меньше sizeof(void *), p2 может быть смещено для записи void * значение p1. Дополнительный код необходим, чтобы убедиться, что alignment по крайней мере равен sizeof(void *). В реальных системах это не проблема, потому что malloc() должен возвращать указатели, которые правильно выровнены для всех базовых c типов, включая void *.

Причина побитовая * 1043 Операторы * и ~ предпочтительнее, это один из способов эффективности: для x целое число без знака и alignment степень 2 x & (alignment - 1) эквивалентна x % alignment, но большинство ЦП гораздо быстрее вычисляют с побитовая маска, чем с делением, и компилятор не может сделать предположение, что alignment является степенью 2, поэтому он скомпилирует ваш код, используя гораздо более медленную инструкцию целочисленного деления.

Кроме того, ваши вычисления неверны: если p1 не выровнен, offset (вычисляется как (size_t)(p1) % alignment) может достигать alignment - 1, поэтому p2 может быть так же близко к p1, как 1 байт, поэтому p2[-1] = p1; записывает перед началом выделенного пространства.

Вот модифицированная версия: 

#include <stdint.h>
#include <stdlib.h>

void *aligned_malloc(size_t size, size_t alignment) {
    // alignment must be a power of 2
    //assert(alignment != 0 && (alignment & (alignment - 1)) == 0);
    void *p1;     // allocated block
    void **p2;    // aligned block
    size_t slack; // amount of extra memory to allocate to ensure proper alignment
                  // and space to save the original pointer returned by malloc.
    //compute max(alignment - 1, sizeof(void*) - 1) without testing:
    size_t alignment_mask = (alignment - 1) | (sizeof(void *) - 1);
    slack = alignment_mask + sizeof(void *);
    if ((p1 = malloc(size + slack)) == NULL)
        return NULL;
    p2 = (void **)(void *)(((uintptr_t)p1 + slack) & ~alignment_mask);
    p2[-1] = p1;
    return p2;
}
3 голосов
/ 01 мая 2020

Возможно, потому что alignment - это переменная с неизвестным (для компилятора) значением, что означает, что компилятор не может легко сделать это более простой операцией.

Битовые операции проще и эффективнее, чем арифметика c (особенно деление), необходимая оператору %.

...