Как реализовать memmove в стандарте C без промежуточной копии?

Question

Со страницы man в моей системе:

void * memmove (void * dst, const void * src, size_t len);

ОПИСАНИЕ
Функция memmove() копирует len байтов из строки src в строку dst.
Две строки могут перекрываться; копия всегда делается в неразрушающем
манера.

Из стандарта C99:

6.5.8.5 Когда сравниваются два указателя, результат зависит от относительного расположения в адресном пространстве указанных объектов. Если два указателя на объект или неполный тип оба указывают на один и тот же объект, или оба указывают один за последним элементом одного и того же объекта массива, они сравниваются равными. Если указанные объекты являются членами одного и того же агрегатного объекта, указатели на элементы структуры, объявленные позже, сравниваются больше, чем указатели, на элементы, объявленные ранее в структуре, а указатели на элементы массива с большими значениями нижнего индекса сравниваются больше, чем указатели, на элементы того же массива. с более низкими значениями индекса. Все указатели на члены одного и того же объекта объединения сравниваются одинаково. Если выражение P указывает на элемент объекта массива, а выражение Q указывает на последний элемент того же объекта массива, выражение указателя Q+1 сравнивает больше чем P, Во всех остальных случаях поведение не определено.

Акцент мой.

Аргументы dst а также src может быть преобразован в указатели на char чтобы устранить строгие проблемы с алиасами, но возможно ли сравнить два указателя, которые могут указывать внутри разных блоков, чтобы сделать копию в правильном порядке, если они указывают внутри одного и того же блока?

Очевидное решение if (src < dst), но это не определено, если src а также dst указать на разные блоки. "Не определено" означает, что вы даже не должны предполагать, что условие возвращает 0 или 1 (это можно было бы назвать "неопределенным" в словаре стандарта).

Альтернатива if ((uintptr_t)src < (uintptr_t)dst), что по крайней мере не определено, но я не уверен, что стандарт гарантирует, что когда src < dst определяется, это эквивалентно (uintptr_t)src < (uintptr_t)dst), Сравнение указателей определяется из арифметики указателей. Например, когда я читаю раздел 6.5.6 о добавлении, мне кажется, что арифметика указателя может идти в направлении, противоположном uintptr_t арифметика, то есть, что совместимый компилятор может иметь, когда p имеет тип char*:

((uintptr_t)p)+1==((uintptr_t)(p-1)

Это только пример. Вообще говоря, при преобразовании указателей в целые числа, похоже, гарантируется очень мало.

Это чисто академический вопрос, потому что memmove предоставляется вместе с компилятором. На практике авторы компилятора могут просто способствовать сопоставлению неопределенного указателя с неопределенным поведением или использовать соответствующую прагму, чтобы заставить их компилятор скомпилировать их memmove правильно. Например, эта реализация имеет следующий фрагмент:

if ((uintptr_t)dst < (uintptr_t)src) {
            /*
             * As author/maintainer of libc, take advantage of the
             * fact that we know memcpy copies forwards.
             */
            return memcpy(dst, src, len);
    }

Я все еще хотел бы использовать этот пример в качестве доказательства того, что стандарт заходит слишком далеко с неопределенным поведением, если это правда, что memmove не может быть эффективно реализовано в стандарте C. Например, никто не пометил галочкой ответ на этот вопрос SO.

Answer 1

Я думаю, что вы правы, это невозможно реализовать memmove эффективно в стандарте C.

Я думаю, что единственный действительно портативный способ проверить, перекрываются ли регионы, - это что-то вроде этого:

[Редактировать: глядя на это намного позже, я думаю, что это должно быть dst+len-1 в конце второй строки. Но я не могу потрудиться проверить это, поэтому я уйду, как сейчас, возможно, я знал, о чем говорил в первый раз.]

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len) {
      // they overlap, so now we can use comparison,
      // and copy forwards or backwards as appropriate.
      ...
      return dst;
    }
}
// No overlap, doesn't matter which direction we copy
return memcpy(dst, src, len);

Вы не можете реализовать либо memcpy или же memmove все это эффективно в переносимом коде, потому что реализация для конкретной платформы, скорее всего, пойдет вам в ногу с тем, что вы делаете Но портативный memcpy по крайней мере, выглядит правдоподобно.

C++ ввел указатель специализации std::less, который определен для работы с любыми двумя указателями одного типа. Теоретически это может быть медленнее, чем <, но, очевидно, для несегментированной архитектуры это не так.

C не имеет такого понятия, поэтому в некотором смысле стандарт C++ согласен с вами, что C не имеет достаточно определенного поведения. Но тогда C++ это нужно для std::map и так далее. Скорее всего, вы захотите реализовать std::map (или что-то вроде этого) без знания реализации, чем вы хотели бы реализовать memmove (или что-то подобное) без знания реализации.

Answer 2

Я полагаю, что для того, чтобы две области памяти были действительными и перекрывали друг друга, вам нужно оказаться в одной из определенных ситуаций, описанных в 6.5.8.5. То есть две области массива: объединение, структура и т. Д.

Причина, по которой другие ситуации не определены, заключается в том, что два разных объекта могут даже не находиться в одном и том же виде памяти с одним и тем же типом указателя. На архитектурах ПК адреса обычно представляют собой просто 32-разрядные адреса в виртуальной памяти, но C поддерживает все виды причудливых архитектур, где память не имеет ничего общего с этим.

Причина того, что C оставляет вещи неопределенными, заключается в том, чтобы дать свободу разработчикам компилятора, когда ситуацию не нужно определять. Способ чтения 6.5.8.5 - это параграф, подробно описывающий архитектуры, которые C хочет поддерживать, когда сравнение указателей не имеет смысла, если только оно не находится внутри одного и того же объекта.

Кроме того, компоновщик предоставляет memmove и memcpy в том, что они иногда записываются в настроенной сборке для целевого процессора с использованием специальной инструкции. Они не предназначены для того, чтобы их можно было реализовать на С с той же эффективностью.

Answer 3

Начнем с того, что стандарт С славится проблемами в таких деталях. Частично проблема заключается в том, что C используется на нескольких платформах, и стандарт пытается быть достаточно абстрактным, чтобы охватить все текущие и будущие платформы (которые могут использовать некоторую запутанную структуру памяти, которая превосходит все, что мы когда-либо видели). Существует много неопределенного или специфичного для реализации поведения, чтобы авторы компилятора могли "делать правильные вещи" для целевой платформы. Включение деталей для каждой платформы было бы непрактичным (и постоянно устаревшим); вместо этого стандарт C оставляет за собой право составителю компилятора документировать, что происходит в этих случаях. "Неуказанное" поведение означает только то, что стандарт C не определяет, что происходит, не обязательно, что результат не может быть предсказан. Результат обычно все еще предсказуем, если вы прочитаете документацию для вашей целевой платформы и вашего компилятора.

Поскольку определение того, указывают ли два указателя на один и тот же блок, сегмент памяти или адресное пространство, зависит от того, как распределена память для этой платформы, спецификация не определяет способ сделать это определение. Предполагается, что компилятор знает, как сделать это определение. В той части спецификации, которую вы цитировали, говорилось, что результат сравнения указателей зависит от "относительного расположения указателей в адресном пространстве". Обратите внимание, что "адресное пространство" здесь является единственным. Этот раздел относится только к указателям, которые находятся в одном и том же адресном пространстве; то есть указатели, которые прямо сопоставимы. Если указатели находятся в разных адресных пространствах, то результат не определен стандартом C, а вместо этого определяется требованиями целевой платформы.

В случае memmoveразработчик обычно сначала определяет, сопоставимы ли адреса напрямую. Если нет, то остальная часть функции зависит от платформы. В большинстве случаев достаточно находиться в разных пространствах памяти, чтобы гарантировать, что области не перекрываются, и функция превращается в memcpy, Если адреса прямо сопоставимы, то это просто процесс копирования байтов, начиная с первого байта и заканчивая или начиная с последнего байта и возвращаясь назад (в зависимости от того, какой из них будет безопасно копировать данные без каких-либо помех).

В целом, стандарт C оставляет много преднамеренно неопределенных, где он не может написать простое правило, которое работает на любой целевой платформе. Тем не менее, стандартные писатели могли бы лучше объяснить, почему некоторые вещи не определены, и использовать более описательные термины, такие как "зависящие от архитектуры".

Answer 4

Вот еще одна идея, но я не знаю, правильно ли это. Чтобы избежать O(len) цикл в ответе Стива, можно положить его в #else пункт о #ifdef UINTPTR_MAX с приведением кuintptr_t реализация. При условии, что актерский состав unsigned char * в uintptr_t коммутирует с добавлением целочисленных смещений всякий раз, когда смещение является допустимым с указателем, это делает сравнение указателя четко определенным.

Я не уверен, определяется ли эта коммутативность стандартом, но это имело бы смысл, поскольку оно работает, даже если только младшие биты указателя являются действительным числовым адресом, а верхние биты - своего рода черным ящиком.

Answer 5

Я все еще хотел бы использовать этот пример в качестве доказательства того, что стандарт заходит слишком далеко с неопределенным поведением, если это правда, что memmove не может быть эффективно реализован в стандарте C

Но это не доказательство. Нет абсолютно никакого способа гарантировать, что вы можете сравнить два произвольных указателя на произвольной архитектуре машины. Поведение такого сравнения указателей не может регулироваться стандартом C или даже компилятором. Я мог бы представить машину с сегментированной архитектурой, которая могла бы давать разные результаты в зависимости от того, как сегменты организованы в ОЗУ, или даже могла бы выдать исключение при сравнении указателей на разные сегменты. Вот почему поведение "неопределено". Одна и та же программа на одной и той же машине может давать разные результаты от запуска к запуску.

Часто данное "решение" memmove(), использующее отношения двух указателей для выбора, копировать ли это с начала до конца или с конца на начало, работает, только если все блоки памяти выделены из одного и того же адресного пространства. К счастью, это обычно так, хотя это было не во времена 16-битного кода x86.