Как проверить, находится ли значение указателя в заданной области памяти

https://blogs.msdn.microsoft.com/oldnewthing/20170927-00/?p=97095
  • Перевод
Пусть у нас есть регион/область памяти, заданный с помощью двух переменных, например:

byte* regionStart;
size_t regionSize;

Требуется проверить, находится ли значение указателя в пределах этого диапазона. Возможно, вашим первым побуждением будет написать так:

if (p >= regionStart && p < regionStart + regionSize)

Но гарантирует ли стандарт ожидаемое поведение этого кода?

Соответствующий пункт стандарта языка C (6.5.8 Операторы отношения)(1) гласит следующее:

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

Теперь вспомним, что язык C предназначался для работы с широким спектром архитектур, многие из которых уже стали музейными экспонатами. По этой причине он крайне консервативен в отношении выбора допустимых действий, так как необходимо оставить возможность писать программы на C для устаревших систем. (Хотя в свое время они были вполне передовыми.)

Тем не менее при выделении памяти возможно появление такого указателя, который будет удовлетворять нашему условию, хотя в действительности он не будет ссылаться на заданную область. Такое случится, например, при работе на процессоре 80286 в защищенном режиме, который использовался операционными системами Windows 3.x в стандартном режиме и OS/2 1.x.

Указатель в такой системе представляет собой 32-битное значение, состоящее из двух частей по 16 бит, — его принято записывать как XXXX:YYYY. Первая 16-битная половина (XXXX) — это «селектор», который служит для выбора сегмента памяти размером 64 Кбайт. Вторая 16-битная половина (YYYY) — «смещение», с помощью которого выбирается байт внутри сегмента, заданного первой половиной. (На самом деле этот механизм сложнее, но в рамках данного обсуждения обойдемся таким объяснением.)

Блоки памяти размером больше 64 Кбайт разбиваются на сегменты по 64 Кбайт. Для перемещения к следующему сегменту необходимо прибавить 8 к селектору текущего сегмента. Например, байт, следующий за 0101:FFFF, записывается как 0109:0000.

Но почему прибавлять надо именно 8? Почему нельзя просто увеличивать селектор на один? Дело в том, что младшие три бита селектора используются для других целей. В частности, самый младший бит селектора служит для выбора таблицы селекторов. Касаться битов 1 и 2 мы здесь не будем, так как они не имеют отношения к нашему вопросу. Для удобства просто представим, что они всегда установлены в ноль.(2)

Соответствие селекторов физическим адресам памяти описывается двумя таблицами: Глобальной таблицей дескрипторов (Global Descriptor Table; определяет сегменты памяти, общие для всех процессов) и Локальной таблицей дескрипторов (Local Descriptor Table; определяет сегменты памяти, выделенные в личное пользование конкретному процессу). Таким образом, селекторы для локальной памяти процесса — 0001, 0009, 0011, 0019 и т.д., а селекторы для глобальной памяти — 0008, 0010, 0018, 0020 и т.д. (Селектор 0000 является зарезервированным.)

Хорошо, теперь мы можем построить контрпример. Пусть regionStart = 0101:0000, а regionSize = 0x00020000. Это означает, что диапазон защищенных адресов составляет с 0101:0000 по 0101:FFFF и с 0109:0000 по 0109:FFFF. Кроме того, regionStart + regionSize = 0111:0000.

А теперь представим, что в диапазоне 0108:0000 выделяется сегмент глобальной памяти, — на то, что это глобальная память, указывает четное число в селекторе.

Заметьте, что область глобальной памяти не входит в диапазон защищенных адресов, однако значение указателя на этот участок удовлетворяет неравенству 0101:0000? 0108:0000 < 0111:0000.

Еще немного текста: Наша проверка может провалиться даже на архитектурах с плоской моделью памяти. Современные компиляторы слишком охотно оптимизируют неопределенное поведение. Обнаружив сравнение указателей, они вправе предположить, что эти указатели ссылаются на один и тот же составной объект или массив (либо на позицию за последним элементом массива), поскольку любой другой вид сравнения приводит к неопределенному поведению. В нашем случае, если regionStart указывает на начало массива или составного объекта, то корректно сравниваться с ним могут только указатели вида regionStart, regionStart + 1, regionStart + 2, ..., regionStart + regionSize. Все они удовлетворяют условию p >= regionStart и потому могут быть оптимизированы, в результате чего компилятор упрощает нашу проверку до следующего кода:

if (p < regionStart + regionSize)

Теперь условию будут удовлетворять все указатели, значение которых меньше regionStart.

(Вы можете столкнуться с этой ситуацией, если — как автор исходного вопроса, ответом на который является данная статья, — выделяете область памяти с помощью выражения regionStart = malloc(n) либо если выделенная область используется как пул preallocated объектов для быстрого доступа и нужно решить, освобождать ли указатель с помощью функции free.)

Мораль: Данный код небезопасен — даже на архитектурах с плоской моделью памяти.

Но не все так плохо: Результат преобразования указателя в целочисленный тип зависит от используемой реализации, а значит, именно она и должна описывать его поведение. Если ваша реализация предполагает получение численного значения линейного адреса объекта, на который ссылается указатель, и вы знаете, что работаете на архитектуре с плоской моделью памяти, то выходом будет сравнивать целые значения вместо указателей. Сравнение целых чисел не имеет таких ограничений, как сравнение указателей.

    if ((uintptr_t)p >= (uintptr_t)regionStart &&
        (uintptr_t)p < (uintptr_t)regionStart + (uintptr_t)regionSize)

Примечания:

  1. Обратите внимание, что «равно» и «не равно» не являются операторами отношения.
  2. Я знаю, что на самом деле это не так, — равными нулю я принимаю их для удобства.

(Данная статья основана на моем комментарии на StackOverflow.)

Обновлено: Уточнение: оптимизация «начала области памяти» производится только тогда, когда указатель regionStart ссылается на начало массива или составного объекта.

This is a translation of «How to check if a pointer is in a range of memory» into Russian. Click the link to see the original English version.
PVS-Studio 196,72
Ищем ошибки в C, C++ и C# на Windows и Linux
Поделиться публикацией
Похожие публикации
Комментарии 16
  • +1
    Выглядит достаточно странно. Как в этом случае должны работать функции типа memset, strcpy и прочие, если нет гарантии, что проход по указателю корректно выдаст все элементы подряд?
    • +3
      проход по указателю корректно выдаст все элементы подряд, именно так. Здесь нет противоречия
      • 0
        Противоречия тут нет. Указанные функции допустимо вызывать при условии, что все подлежащие изменению/копированию данные находятся в пределах одного и того же массива, т.е. что все вычисляемые в процессе работы функции значения указателей допустимо вычислять.
      • 0
        Не уверен, что получился удачный перевод: мало голосов и тихо. Поэтому для оживления приглашаю посмотреть запись нашего нового доклада: C++ CoreHard Autumn 2017, Поиск уязвимостей с использованием статического анализа кода (доклад с этой статьей никак не связан).

        И заодно вопрос: Сделать какую-то диагностику в PVS-Studio на тему статьи это безумие, да?
        • +3
          Сделать какую-то диагностику в PVS-Studio на тему статьи это безумие, да?

          Да)
          • +2
            Похоже, вам нужно добавить целый класс диагностик "Безумие?! Нет, ЭТО СПААААРТААА!!!!!"
            И сбрасывать все не прошедшие диагностику файлы в Корзину.
            • +1
              Возможно, «мало» и «тихо», потому что в тексте нет реального примера «доламывания» не соответствующего Стандарту кода оптимизирующим компилятором.
            • 0

              Может ли начальный вариант компилятор преобразовать не только к:


              if (p < regionStart + regionSize)

              но, также, и к (нет, ну а вдруг на целевой архитектуре < работает намного медленнее, чем !=):


              if (p != regionStart + regionSize)

              Ход рассуждений
              int in_region(int* p)
              {
                  return p >= regionStart && p < regionStart + regionSize;
              }

              можно преобразовать в (как-то так, на C я не пишу):


              int in_region(int* p)
              {
                  if (p == regionStart + regionSize)
                      return 0;
              
                  int* x = regionStart;
                  while (x < regionStart + regionSize)
                  {
                      if (x == p)
                          return 1;
                      else
                          ++x;
                  }
              
                  UndeffinedBehaviorDestroyTheWorldNotImplementedYet();
              }

              т.е.:


              • либо p указывает на 1 елемент за пределами массива (возвращаем 0)
              • либо указывает в пределах массива (возвращаем 1)
              • либо указывает в любое другое место и тогда компилятор может делать что угодно, ибо испольовать <, <=, >, >= в этом случае нельзя

              ну… поскольку ub в программах не существует, то можно оптимизировать до:


              int in_region(int* p)
              {
                  if (p == regionStart + regionSize)
                      return 0;
              
                  return 1;
              }

              или же:


              int in_region(int* p)
              {
                  return p != regionStart + regionSize;
              }

              Или я что-то не учёл?

              • –5
                потому могут быть оптимизированы, в результате чего компилятор упрощает нашу проверку до следующего кода:

                if (p < regionStart + regionSize)

                Не оптимизирует, если компилятор не совсем идиот. Контрпример в compiler explorer.
                • +2
                  Хорошо, теперь мы можем построить контрпример. Пусть regionStart = 0101:0000, а regionSize = 0x00020000.

                  Пример (и весь его последующий анализ, соответственно) некорректен, в 16-бит системе не может быть regionSize больше чем 0x10000 (на самом деле и это число не влезет в 16-битный size_t, но это уже проблемы языка, а сегмент такого размера сделать всё же можно, а вот больше — нет). Селектор это индекс сегмента в весьма произвольной таблице, а не линейный номер участка памяти.

                  • 0
                    if ((uintptr_t)p >= (uintptr_t)regionStart &&
                       (uintptr_t)p < (uintptr_t)regionStart + (uintptr_t)regionSize)

                    Этот вариант, в целом, хороший, но иногда может и создать проблему, если кто-то захочет использовать вместо реального regionSize какое-то абстрактное большое число (допустимость этого — отдельная тема). А ещё он может доставить проблемы уже в полностью законном случае — если конец проверяемой области памяти совпадает с концом адресного пространства (p+regionSize=0x100000000 для 32бит превратится в 0). Вариант, который ничем не уступает процитированному, но лишен указанного недостатка:


                    if ((uintptr_t)p >= (uintptr_t)regionStart &&
                       (uintptr_t)p - (uintptr_t)regionStart < (uintptr_t)regionSize)

                    А если сделать -fno-strict-overflow то можно ещё и опустить первую половину условия (но это уже некоторые могут посчитать плохим).

                    • 0
                      Это ж беззнаковый тип, ему no-strict-overflow не нужен.
                    • 0
                      А в стандартных библиотеках этим замарачиваются?
                      • 0
                        да, в стандартных библиотеках приходится заморачиваться десятками вещей, с которыми обычный пользователь библиотеки возможно никогда не встретится: habrahabr.ru/company/yandex/blog/323972/#comment_10133110
                      • –1
                        Понял, спасибо.
                        • –2
                          286-й процессор в защищенном режиме и программирование для него на си. Вообще, это еще тот геморрой. Эксклюзив.
                          Компилятор с си (родной для полуоси) генерировал код как для реального, так и для защищенного режима, но он также имел руководство программиста толщиной в пять K&R, где черным по белому было написано что-то вроде следующего (как я по памяти помню) — «чтобы сравнивать разнотиповые указатели, их должно (will) приводить к обобщенным (generic) указателям типа void *, однако компилятор в режиме сборки непривилегированных программ по умолчанию соответсвующий кастинг делает автоматом, поскольку сложно представить себе случай, когда понадобилось бы иное. На более низком уровне был системный вызов к ядру AllocMem(), который тем не менее, как это было описано в руководстве, выделял память физически непрерывным куском. Разместить объект в двух таких даже смежных экстентах было невозможно, поэтому указатели всегда пробегали непрерывный ряд значений.
                          В случае стека было одно отличие — сегмент рос при необходимости, тем не менее обеспечивалась непрерывная логическая адресация в его пределах.
                          В случае 32-разрядных систем (за исключением бортовой экзотики, для которой-то и компиляторов с языка си нет) указатель содержит чистый логический/виртуальный адрес. Это просто порядковый номер байта, на который он указывает в непрерывной области адресов. Этот логический адрес формируется в процессе сегментации, происходит все это внутри процессора и недоступно прикладному программисту.
                          Адресное пространство процесса непрерывно и это принципиально. Как там и что отображается на физические адреса при выделении физической или другой какой памяти, на непривилегированном уровне узнать невозможно. Это вообще знает только та часть ядра, которая непосредственно занимается виртуальной памятью, и больше никто.
                          Если Вы не доверяете своему компилятору или супераккуратист, просто используйте в сравнениях кастинг на void *. Тип void * всегда имеет гранулярность минимально адресуемого объекта — байта.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое