Exponiendo NSDictionary

Exponer NSDictionary

Las tablas hash son simplemente increíbles. Hasta el día de hoy me parece fascinante que se pueda recuperar un objeto correspondiente a una clave arbitraria en un tiempo constante. Aunque iOS 6.0 introdujo una tabla hash explícita, es NSDictionary el que se utiliza casi exclusivamente para el almacenamiento asociativo. Las tablas hash son geniales. A día de hoy me sigue pareciendo muy interesante conseguir el objeto correspondiente a cualquier clave en un periodo de tiempo fijo. Aunque iOS 6.0 introdujo tablas hash explícitas, NSDictionary se usa casi exclusivamente para almacenamiento asociativo.

NSDictionary no hace ninguna promesa sobre su implementación interna. No tendría mucho sentido que un diccionario almacenara sus datos de forma completamente aleatoria. Sin embargo, esta suposición no responde a la pregunta clave: ¿NSDictionary utiliza una tabla hash? Esto es lo que he decidido investigar. NSDictionary no hace promesas sobre su implementación interna. No tiene sentido que un diccionario almacene datos de forma completamente aleatoria. Sin embargo, esta suposición no responde a la pregunta clave: ¿NSDictionary utiliza una tabla hash? Eso es lo que decidí investigar.

¿Por qué no abordar el NSMutableDictionary con todas las funciones? Un diccionario mutable es, comprensiblemente, mucho más complejo y la cantidad de desmontaje por la que habría tenido que pasar fue aterradora. El NSDictionary normal todavía proporcionaba un desafío de descifrado ARM64 no trivial. A pesar de ser inmutable, la clase tiene algunos detalles de implementación muy interesantes que deberían hacer que el siguiente viaje sea agradable. ¿Por qué no simplemente utilizar un NSMutableDictionary con todas las funciones? Es comprensible que un diccionario mutable sea mucho más complejo y la cantidad de factorización que necesitaría hacer sería horrenda. Plain NSDictionary todavía presenta un importante desafío de decodificación ARM64. Aunque esta clase es inmutable, tiene algunos detalles de implementación muy interesantes que deberían hacer que el proceso siguiente sea agradable.

Esta publicación de blog tiene un repositorio complementario que contiene fragmentos de código discutidos. Si bien toda la investigación se basó en el SDK de iOS 7.1 dirigido a un dispositivo de 64 bits, ni iOS 7.0 ni los dispositivos de 32 bits afectan los hallazgos. Esta publicación de blog tiene un repositorio adjunto que contiene los fragmentos de código discutidos. Si bien toda la investigación se basó en el SDK de iOS 7.1 para dispositivos de 64 bits, ni iOS 7.0 ni los dispositivos de 32 bits afectaron los hallazgos.

La clase Clase

Muchas clases de Foundation son grupos de clases y NSDictionary no es una excepción. Durante bastante tiempo, NSDictionary usó CFDictionary como implementación predeterminada; sin embargo, a partir de iOS 6.0 las cosas han cambiado: Muchas clases básicas son grupos de clases y NSDictionary no es una excepción. Durante bastante tiempo, NSDictionary usó CFDictionary como implementación predeterminada; sin embargo, a partir de iOS 6.0, las cosas han cambiado:

(lldb) po [[NSDictionary new] class]
__NSDictionaryI

De manera similar a __NSArrayM, __NSDictionaryI se encuentra dentro del marco de CoreFoundation, a pesar de presentarse públicamente como parte de Foundation. La ejecución de la biblioteca a través de class-dump genera el siguiente diseño de ivar: Al igual que __NSArrayM, __NSDictionaryI vive dentro del marco de CoreFoundation, aunque se expone públicamente como parte de Foundation. Al ejecutar la biblioteca a través de un volcado de clase se produce el siguiente diseño de ivar:

@interface __NSDictionaryI : NSDictionary
{
    NSUIngeter _used:58;
    NSUIngeter _szidx:6;
}

Es sorprendentemente corto. No parece haber ningún indicador ni del almacenamiento de llaves ni de objetos. Como veremos pronto, __NSDictionary literalmente guarda su almacenamiento para sí mismo. Es sorprendentemente corto. No parece haber ningún indicio de claves o almacenamiento de objetos. Como veremos en breve, __NSDictionary literalmente contiene su almacenamiento.

El almacenamiento Almacenamiento

Creación de instancia creación de instancia

Para comprender dónde guarda __NSDictionaryI su contenido, hagamos un recorrido rápido por el proceso de creación de instancias. Sólo hay un método de clase que es responsable de generar nuevas instancias de __NSDictionaryI. Según class-dump, el método tiene la siguiente firma: Para comprender dónde se guarda el contenido de __NSDictionaryI, echemos un vistazo rápido al proceso de creación de instancias. Sólo hay un método de clase responsable de generar nuevas instancias de __NSDictionaryI. Según class-dump, este método tiene las siguientes características:

+ (id)__new:(const id *)arg1:(const id *)arg2:(unsigned long long)arg3:(_Bool)arg4:(_Bool)arg5;

Se necesitan cinco argumentos, de los cuales sólo se nombra el primero. En serio, si lo usara en una declaración @selector, tendría la forma @selector(__new:::::). matriz de objetos y número de claves (objetos) respectivamente. Tenga en cuenta que las matrices de claves y objetos se intercambian en comparación con la API pública que toma la forma de: Se necesitan cinco parámetros, de los cuales sólo se nombra el primero. En serio, si lo usa en una declaración @selector, tendrá la forma @selector(__new:::::). Los primeros tres parámetros se pueden deducir fácilmente estableciendo un punto de interrupción en el método y husmeando en el contenido de los registros x2, x3 y x4 que contienen la matriz de claves, la matriz de objetos y el recuento de claves (objeto) respectivamente. Tenga en cuenta que las claves y las matrices de objetos se intercambian en comparación con la API pública que toma la forma:

+ (instancetype)dictionaryWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt;

No importa si un argumento está definido como const id * o const id [], ya que las matrices se descomponen en punteros cuando se pasan como argumentos de función. No importa si el parámetro está definido como const id * o const id[], ya que la matriz se descompondrá en un puntero cuando se pase como parámetro de función.Con tres argumentos cubiertos, nos quedan los dos parámetros booleanos no identificados. He investigado un poco el ensamblaje y obtuve los siguientes resultados: el cuarto argumento rige si las claves deben copiarse y el último decide si los argumentos no deben conservarse. Ahora podemos reescribir el método con parámetros con nombre: Con tres parámetros, nos quedan dos parámetros booleanos no identificados. Investigué un poco en el ensamblaje y esto es lo que encontré: el cuarto parámetro controla si la clave debe copiarse y el último parámetro determina si el parámetro no debe conservarse. Ahora podemos anular este método con parámetros con nombre:

+ (id)__new:(const id *)keys :(const id *)objects :(unsigned long long)count :(_Bool)copyKeys :(_Bool)dontRetain;

Desafortunadamente, no tenemos acceso explícito a este método privado, por lo que al utilizar los medios habituales de asignación, los dos últimos argumentos siempre se establecen en YES y NO respectivamente. Sin embargo, es interesante que __NSDictionaryI sea capaz de realizar un control de teclas y objetos más sofisticado. Desafortunadamente, no podemos acceder explícitamente a este método privado, por lo que al utilizar el método de asignación normal, los dos últimos parámetros siempre se establecen en SÍ y NO respectivamente. No obstante, es interesante observar que __NSDictionaryI es capaz de proporcionar controles de objetos y claves más complejos.

####Variables de instancia indexadas por ivars indexados

Al hojear el desmontaje de + __new:::::, se revela que tanto malloc como calloc no se encuentran por ningún lado. En cambio, el método llama a __CFAllocateObject2 pasando la clase __NSDictionaryI como primer argumento y el tamaño de almacenamiento solicitado como segundo. Bajar al mar de ARM64 muestra que lo primero que hace __CFAllocateObject2 es llamar a class_createInstance con exactamente los mismos argumentos. Examinar la descomposición de + __new:::: revela que ni malloc ni calloc existen. En cambio, el método llama a __CFAllocateObject2 y pasa la clase __NSDictionaryI como primer parámetro y el tamaño de almacenamiento solicitado como segundo parámetro. Entrar en el océano de ARM64 muestra que lo primero que hace __CFAllocateObject2 es llamar a class_createInstance con exactamente los mismos parámetros.

Afortunadamente, en este punto tenemos acceso al código fuente del tiempo de ejecución de Objective-C, lo que facilita mucho la investigación adicional. Afortunadamente, ahora tenemos acceso al código fuente del tiempo de ejecución de Objective-C, lo que facilita la investigación adicional.

La función class_createInstance(Class cls, size_t extraBytes) simplemente llama a _class_createInstanceFromZone ​​pasando a nil como zona, pero este es el paso final de la asignación de objetos. Si bien la función en sí tiene muchas comprobaciones adicionales para diferentes circunstancias, su esencia se puede cubrir con solo tres líneas: La función class_createInstance(Class cls, size_t extraBytes) simplemente llama a _class_createInstanceFromZone y pasa nil como zona, pero este es el último paso de la asignación de objetos. Aunque la función en sí tiene muchas comprobaciones adicionales para diferentes situaciones, su esencia se puede describir en tres líneas:

_class_createInstanceFromZone(Class cls, size_t extraBytes, void *zone)
{
    ...
    size_t size = cls->alignedInstanceSize() + extraBytes;
    ...
    id obj = (id)calloc(1, size);
    ...
    return obj;
}

El argumento extraBytes no podría haber sido más descriptivo. Es literalmente la cantidad de bytes adicionales que inflan el tamaño de instancia predeterminado. Como beneficio adicional, observe que es la llamada calloc la que garantiza que todos los ivars se pongan a cero cuando se asigna el objeto. Un argumento de un terabyte no podría ser mejor. En realidad, son los bytes adicionales los que aumentan el tamaño de instancia predeterminado. Además, tenga en cuenta que la llamada calloc garantiza que todos los ivars se pongan a cero cuando se asigne el objeto.

La sección de ivars indexados no es más que un espacio adicional que se encuentra al final de los ivars regulares: La parte del índice ivars no es más que un espacio extra al final de los ivars regulares:

Asignar objetos

Asignar espacio por sí solo no suena muy emocionante, por lo que el tiempo de ejecución publica un descriptor de acceso: Asignar espacio individualmente no suena interesante, por lo que el tiempo de ejecución publica un descriptor de acceso:

void *object_getIndexedIvars(id obj)

No hay ningún tipo de magia en esta función, simplemente devuelve un puntero al comienzo de la sección de ivars indexados: No hay nada mágico en esta función, simplemente devuelve un puntero al comienzo de la sección de ivars del índice:

Sección de ivars indexados

Hay algunas cosas interesantes sobre los ivars indexados. En primer lugar, cada instancia puede tener una cantidad diferente de bytes adicionales dedicados. Esta es exactamente la característica que utiliza __NSDictionaryI. Hay algunas cosas interesantes sobre la indexación de ivars. Primero, cada instancia puede tener una cantidad diferente de bytes adicionales. Esto es exactamente lo que usa __NSDictionaryI.

En segundo lugar, proporcionan un acceso más rápido al almacenamiento. Todo se reduce a ser compatible con el caché. En términos generales, saltar a ubicaciones de memoria aleatorias (eliminando la referencia de un puntero) puede resultar costoso. Dado que se acaba de acceder al objeto (alguien ha llamado a un método), es muy probable que sus ivars indexados hayan aterrizado en la caché. Al mantener todo lo que se necesita muy cerca, el objeto puede proporcionar el mejor rendimiento posible. En segundo lugar, proporcionan un acceso al almacenamiento más rápido. Todo se reduce a la compatibilidad con el caché. En general, saltar a una ubicación de memoria aleatoria (desreferenciando un puntero) puede resultar costoso. Dado que se acaba de acceder al objeto (alguien llamó a un método), lo más probable es que su índice ivar ya esté en el caché. Al mantener todo lo necesario muy cerca, los objetos pueden proporcionar el mejor rendimiento posible.

Finalmente, los ivars indexados se pueden utilizar como una burda medida defensiva para hacer que el interior del objeto sea invisible para las utilidades como class-dump. Esta es una protección muy básica ya que un atacante dedicado puede simplemente buscar llamadas object_getIndexedIvars en el desensamblado o probar aleatoriamente la instancia más allá de su sección ivars habitual para ver qué está pasando. Finalmente, los índices ivars se pueden utilizar como una burda medida de defensa para que utilidades como el volcado de clases no puedan ver la estructura interna de un objeto. Esta es una protección muy básica, ya que un atacante dedicado podría simplemente buscar la llamada object_getIndexedIvars en el desensamblado, o probar aleatoriamente la instancia a través de su parte regular de ivars para ver qué está pasando.Si bien los ivars indexados son poderosos, vienen con dos advertencias. En primer lugar, class_createInstance no se puede usar bajo ARC, por lo que tendrás que compilar algunas partes de tu clase con el indicador -fno-objc-arc para que brille. En segundo lugar, el tiempo de ejecución no guarda la información del tamaño de ivar indexado en ninguna parte. Aunque dealloc limpiará todo (como llama internamente a free), debe mantener el tamaño de almacenamiento en algún lugar, suponiendo que utilice un número variable de bytes adicionales. Aunque el índice ivar es poderoso, hay dos puntos a tener en cuenta. Primero, class_createInstance no funciona bajo ARC, por lo que debes compilar algunas partes de la clase con el indicador -fno-objc-arc para que brille. En segundo lugar, la información del tamaño del índice ivar no se guarda en ningún lugar en tiempo de ejecución. Aunque dealloc limpia todo (porque llama gratis internamente), debes preservar el tamaño de almacenamiento, asumiendo que usas una cantidad variable de bytes adicionales.

Buscando claves y recuperando objetos Buscando claves y recuperando objetos

Análisis de ensamblaje Análisis de ensamblaje

Aunque a estas alturas podríamos pinchar en las cajas __NSDictionaryI para descubrir cómo funcionan, la verdad última está en el ensamblaje. En lugar de revisar toda la pared de ARM64, discutiremos el código Objective-C equivalente. Si bien en este punto podemos husmear en las instancias de __NSDictionaryI para ver cómo funcionan, la verdad última reside en el ensamblaje. Discutiremos el código Objective-C equivalente, en lugar del ARM64 completo.

La clase en sí implementa muy pocos métodos, pero creo que el más importante es objectForKey:; esto es lo que vamos a discutir con más detalle. Como de todos modos hice el análisis del montaje, puedes leerlo en una página aparte. Es denso, pero un repaso completo debería convencerte de que el siguiente código es más o menos correcto. La clase en sí implementa muy pocos métodos, pero creo que el más importante es objectForKey: esto es algo que discutiremos con más detalle. Como hice el análisis de compilación, puedes leerlo en una página separada. Es denso, pero el pase completo te hará creer que el código siguiente es más o menos correcto.

El código C Código C

Desafortunadamente, no tengo acceso al código base de Apple, por lo que el siguiente código de ingeniería inversa no es idéntico a la implementación original. Por otro lado, parece estar funcionando bien y todavía tengo que encontrar un caso límite que se comporte de manera diferente en comparación con el método original. Desafortunadamente, no tengo acceso al código base de Apple, por lo que el siguiente código de ingeniería inversa no es idéntico a la implementación original. Por otro lado, parece funcionar bien y no he encontrado ningún caso en el que se comporte de manera diferente al método real.

El siguiente código está escrito desde la perspectiva de la clase __NSDictionaryI : El siguiente código está escrito desde la perspectiva de la clase __NSDictionaryI:

- (id)objectForKey:(id)aKey
{
    NSUInteger sizeIndex = _szidx;
    NSUInteger size = __NSDictionarySizes[sizeIndex];
    
    id *storage = (id *)object_getIndexedIvars(dict);
    
    NSUInteger fetchIndex = [aKey hash] % size;
    
    for (int i = 0; i < size; i++) {
        id fetchedKey = storage[2 * fetchIndex];

        if (fetchedKey == nil) {
            return nil;
        }
        
        if (fetchedKey == aKey || [fetchedKey isEqual:aKey]) {
            return storage[2 * fetchIndex + 1];
        }

        fetchIndex++;
        
        if (fetchIndex == size) {
            fetchIndex = 0;
        }
    }
    
    return nil;
}

Cuando observa más de cerca el código C, puede notar algo extraño en la obtención de claves. Siempre se toma de compensaciones pares, mientras que el objeto devuelto está en el siguiente índice. Este es el claro indicio del almacenamiento interno del __NSDictionaryI: guarda claves y objetos alternativamente: Cuando observa detenidamente el código C, puede notar algunas rarezas en la adquisición de claves. Siempre toma un desplazamiento par y el objeto devuelto está en el siguiente índice. Esta es una falla fatal en el almacenamiento interno de __NSDictionaryI: guarda claves y objetos alternativamente:

Las claves y los objetos se almacenan alternativamente.

Actualización: Joan Lluch proporcionó una explicación muy convincente para este diseño. El código original podría utilizar una serie de estructuras muy simples: Actualización: Joan Lluch dio una explicación muy convincente de este trazado. El código original puede utilizar una matriz de estructuras muy simple:

struct KeyObjectPair {
    id key;
    id object;
};

El método objectForKey: es muy sencillo y le recomiendo que lo repase mentalmente. No obstante, vale la pena señalar algunas cosas. En primer lugar, el ivar _szidx se utiliza como índice en la matriz __NSDictionarySizes, por lo que lo más probable es que signifique “índice de tamaño”. El método objectForKey: es muy simple y te recomiendo que lo repitas mentalmente. No obstante, hay algunos puntos que vale la pena señalar. Primero, el _szidx ivar se usa como índice en la matriz __nsdictionarysize, por lo que lo más probable es que represente el “índice de tamaño”.

En segundo lugar, el único método invocado con la clave pasada es hash. El recordatorio de dividir el valor hash de la clave por el tamaño del diccionario se utiliza para calcular el desplazamiento en la sección de ivars del índice. En segundo lugar, el único método invocado con la clave pasada es el hash. El hash de la clave de recordatorio dividido por el tamaño del diccionario se utiliza para calcular el desplazamiento en la porción ivars del índice.

Si la clave en el desplazamiento es nil, simplemente devolvemos nil, el trabajo está hecho: Si la clave es nula en el desplazamiento, simplemente devolvemos nil y el trabajo está hecho:

Cuando la ranura de la llave está vacía, se devuelve cero

Sin embargo, si la clave en el desplazamiento no es nil, pueden ocurrir ambos casos. Si las claves son iguales, devolvemos el objeto adyacente. Si no son iguales, entonces se produjo la colisión de hash y tenemos que seguir buscando más. __NSDictionaryI simplemente sigue buscando hasta que se encuentre una coincidencia o nil: Sin embargo, ambos casos son posibles si la clave en el desplazamiento no es nula. Si los valores clave son iguales, se devuelven objetos adyacentes. Si no son iguales, se produce una colisión de hash y tenemos que seguir buscando. __nsdictionari sigue buscando hasta que encuentra una coincidencia o nula:

Llave encontrada después de una colisiónEste tipo de búsqueda se conoce como sondeo lineal. Observe cómo __NSDictionaryI envuelve el fetchIndex cuando se alcanza el extremo de almacenamiento. El bucle for está ahí para limitar el número de comprobaciones: si el almacenamiento estuviera lleno y faltara la condición del bucle, seguiríamos buscando para siempre. Esta búsqueda se llama sondeo lineal. Observe cómo __NSDictionaryI envuelve fetchIndex cuando llega al lado de almacenamiento. El bucle for se utiliza para limitar el número de comprobaciones: si la tienda está llena y falta la condición del bucle, seguiremos buscando.

####__NSDictionarySizes y __NSDictionaryCapacities

Ya sabemos que __NSDictionarySizes es una especie de matriz que almacena diferentes tamaños posibles de __NSDictionaryI. Podemos razonar que es una matriz de NSUInteger y, de hecho, si le pedimos a Hopper que trate los valores como enteros sin signo de 64 bits, de repente tiene mucho sentido: Ya sabemos que __nsdictionarysize es una especie de matriz que almacena __NSDictionaryI de diferentes tamaños. Podemos inferir que es una matriz de NSUIntegers y, de hecho, si le pedimos a Hopper que maneje estos valores como enteros sin signo de 64 bits, de repente tiene sentido:

___NSDictionarySizes:
0x00000000001577a8         dq         0x0000000000000000
0x00000000001577b0         dq         0x0000000000000003
0x00000000001577b8         dq         0x0000000000000007
0x00000000001577c0         dq         0x000000000000000d
0x00000000001577c8         dq         0x0000000000000017
0x00000000001577d0         dq         0x0000000000000029
0x00000000001577d8         dq         0x0000000000000047
0x00000000001577e0         dq         0x000000000000007f
...

En una forma decimal más familiar, se presenta como una hermosa lista de 64 números primos que comienzan con la siguiente secuencia: 0, 3, 7, 13, 23, 41, 71, 127. Observe que esos no son números primos consecutivos, lo que plantea la pregunta: ¿cuál es la proporción promedio de los dos números vecinos? En realidad, se trata del 1.637, una coincidencia muy cercana al 1.625, que fue el factor de crecimiento del NSMutableArray. Para obtener detalles sobre por qué se utilizan números primos para el tamaño de almacenamiento, esta respuesta de Stack Overflow es un buen comienzo. En una forma decimal más familiar, representa una buena lista de 64 números primos, comenzando con la siguiente secuencia: 0, 3, 7, 13, 23, 41, 71, 127. Tenga en cuenta que estos no son números primos consecutivos. Esto plantea la pregunta ¿cuál es la razón promedio de dos números adyacentes? En realidad, es de alrededor de 1,637, que está muy cerca del factor de crecimiento de NSMutableArray de 1,625. Para obtener más detalles sobre por qué se utilizan números primos para los tamaños de almacenamiento, esta respuesta de Stack Overflow es un buen comienzo.

Ya sabemos cuánto almacenamiento puede tener __NSDictionaryI, pero ¿cómo sabe qué índice de tamaño elegir en la inicialización? La respuesta está en el método de clase + __new::::: mencionado anteriormente. Al convertir algunas partes del ensamblaje nuevamente a C, se genera el siguiente código: Ya sabemos cuánto almacenamiento puedo tener __NSDictionaryI, pero ¿cómo sabe qué tamaño de índice elegir en el momento de la inicialización? La respuesta está en el método de clase + __new:::: mencionado anteriormente. Al convertir algunas partes del ensamblaje nuevamente a C, se genera el siguiente código:

int szidx;
for (szidx = 0; szidx < 64; szidx++) {
    if (__NSDictionaryCapacities[szidx] >= count) {
        break;
    }
}

if (szidx == 64) {
    goto fail;
}

El método busca linealmente a través de la matriz __NSDictionaryCapacities hasta que el recuento se ajuste al tamaño. Un vistazo rápido a Hopper muestra el contenido de la matriz: Este método busca linealmente en la matriz __nsdictionarycapacity hasta que el recuento coincida con ese tamaño. De un vistazo rápido en Hopper, el contenido de la matriz es el siguiente:

___NSDictionaryCapacities:
0x00000000001579b0         dq         0x0000000000000000
0x00000000001579b8         dq         0x0000000000000003
0x00000000001579c0         dq         0x0000000000000006
0x00000000001579c8         dq         0x000000000000000b
0x00000000001579d0         dq         0x0000000000000013
0x00000000001579d8         dq         0x0000000000000020
0x00000000001579e0         dq         0x0000000000000034
0x00000000001579e8         dq         0x0000000000000055
...

La conversión a base 10 proporciona 0, 3, 6, 11, 19, 32, 52, 85, etc. Observe que esos son números más pequeños que los números primos enumerados anteriormente. Si tuviera que colocar 32 pares clave-valor en __NSDictionaryI, asignará espacio para 41 pares, ahorrando de manera conservadora bastantes espacios vacíos. Esto ayuda a reducir la cantidad de colisiones de hash, manteniendo el tiempo de recuperación lo más constante posible. Aparte del caso trivial de 3 elementos, __NSDictionaryI nunca tendrá su almacenamiento lleno, ocupando en promedio como máximo el 62% de su espacio. La conversión a base 10 proporciona 0, 3, 6, 11, 19, 32, 52, 85, etc. Tenga en cuenta que estos números son más pequeños que los números primos enumerados anteriormente. Si coloca 32 pares clave-valor en __NSDictionaryI, asignará espacio para 41 pares clave-valor, ahorrando de manera conservadora una gran cantidad de espacios vacíos. Esto ayuda a reducir la cantidad de colisiones de hash y mantiene el tiempo de recuperación lo más constante posible. Excepto por el simple caso de 3 elementos, el almacenamiento de __NSDictionaryI nunca está lleno, ocupando hasta el 62% del espacio en promedio.

Como curiosidad, el último valor no vacío de __NSDictionaryCapacities es 0x11089481C742, que es 18728548943682 en base 10. Tendrías que esforzarte mucho para no encajar dentro del límite de recuento de pares, al menos en una arquitectura de 64 bits. Como curiosidad, el último valor no nulo de __nsdictionarycapacity es 0x11089481C742, que en base-10 es 18728548943682. Al menos en arquitecturas de 64 bits, hay que esforzarse mucho para no cumplir con el límite del conteo.

Símbolos no exportados Bandera de no exportación

Si usara __NSDictionarySizes en su código declarándolo como una matriz extern, rápidamente se daría cuenta de que no es tan fácil. El código no se compilaría debido a un error del vinculador: el símbolo __NSDictionarySizes no está definido. Inspeccionando la biblioteca CoreFoundation con la utilidad nm: Si usa __nsdictionarysize en su código declarando __nsdictionarysize como una matriz externa, rápidamente se dará cuenta de que esto no es fácil. El código no se puede compilar debido a un error del vinculador: el símbolo __nsdictionarysize no está definido. Utilice la herramienta nm para comprobar la biblioteca CoreFoundation:

nm CoreFoundation | grep ___NSDictionarySizes

…muestra claramente que los símbolos están ahí (para ARMv7, ARMv7s y ARM64 respectivamente): …muestra claramente la presencia de símbolos (ARMv7, ARMv7s y ARM64 respectivamente):

00139c80 s ___NSDictionarySizes
0013ac80 s ___NSDictionarySizes
0000000000156f38 s ___NSDictionarySizes

Lamentablemente, el manual de nm establece claramente: Desafortunadamente, el manual de nm establece claramente:

Si el símbolo es local (no externo), el tipo del símbolo se representa mediante la letra minúscula correspondiente.Los símbolos de __NSDictionarySizes simplemente no se exportan: están destinados al uso interno de la biblioteca. Investigué un poco para determinar si es posible vincular con símbolos no exportados, pero aparentemente no lo es (¡dígame si es así!). No podemos acceder a ellos. Es decir, no podemos acceder a ellos fácilmente. Los símbolos de __nsdictionarysize no se exportan; son para uso interno de la biblioteca. Investigué un poco y me pregunté si era posible vincular símbolos no exportados, pero aparentemente no es posible (¡dígame si es posible!) y no podemos acceder a ellos. Es decir, no podemos acceder a ellos fácilmente.

Furtivamente en secreto en

Aquí hay una observación interesante: tanto en iOS 7.0 como 7.1, la constante kCFAbsoluteTimeIntervalSince1904 se presenta directamente antes de __NSDictionarySizes: Una observación interesante aquí: en iOS 7.0 y 7.1, la constante kCFAbsoluteTimeIntervalSince1904 aparece directamente antes de __nsdictionarysize:

_kCFAbsoluteTimeIntervalSince1904:
0x00000000001577a0         dq         0x41e6ceaf20000000
___NSDictionarySizes:
0x00000000001577a8         dq         0x0000000000000000

¡Lo mejor de kCFAbsoluteTimeIntervalSince1904 es que se exporta! Agregaremos 8 bytes (tamaño de double) a la dirección de esta constante y reinterpretaremos el resultado como un puntero a NSUInteger: ¡Lo mejor de kcfabsolutetimeintervalvalis desde 1904 es que se exporta! Agregaremos 8 bytes (el doble del tamaño) a la dirección de esta constante y reinterpretaremos el resultado como un puntero a un NSUInteger:

NSUInteger *Explored__NSDictionarySizes = (NSUInteger *)((char *)&kCFAbsoluteTimeIntervalSince1904 + 8);

Luego podemos acceder a sus valores mediante una indexación conveniente: Luego podemos acceder a su valor a través de un índice conveniente:

(lldb) p Explored__NSDictionarySizes[0]
(NSUInteger) $0 = 0
(lldb) p Explored__NSDictionarySizes[1]
(NSUInteger) $1 = 3
(lldb) p Explored__NSDictionarySizes[2]
(NSUInteger) $2 = 7

Este truco es muy frágil y lo más probable es que se rompa en el futuro, pero este es el proyecto de prueba, por lo que está perfectamente bien. Este truco es muy frágil y lo más probable es que se rompa en el futuro, pero es un proyecto de prueba, por lo que es perfecto.

__NSDictionaryI Características __NSDictionaryI Características

Ahora que hemos descubierto la estructura interna de __NSDictionaryI, podemos usar esta información para descubrir por qué las cosas funcionan como funcionan y qué consecuencias imprevistas introduce la implementación actual de __NSDictionaryI. Ahora que hemos descubierto la estructura interna de __NSDictionaryI, podemos usar esta información para descubrir por qué las cosas funcionan como lo hacen y qué consecuencias imprevistas tiene la implementación actual de __NSDictionaryI.

Código de impresión Código de impresión

Para facilitar un poco nuestra investigación, crearemos un método de categoría auxiliar NSDictionary que imprimirá el contenido de la instancia. Para facilitar nuestra investigación, crearemos un método de categoría NSDictionary auxiliar que imprimirá el contenido de la instancia.

- (NSString *)explored_description
{
    assert([NSStringFromClass([self class]) isEqualToString:@"__NSDictionaryI"]);
    
    BCExploredDictionary *dict = (BCExploredDictionary *)self;

    NSUInteger count = dict->_used;
    NSUInteger sizeIndex = dict->_szidx;
    NSUInteger size = Explored__NSDictionarySizes[sizeIndex];
    
    __unsafe_unretained id *storage = (__unsafe_unretained id *)object_getIndexedIvars(dict);
    
    NSMutableString *description = [NSMutableString stringWithString:@"\n"];
    
    [description appendFormat:@"Count: %lu\n", (unsigned long)count];
    [description appendFormat:@"Size index: %lu\n", (unsigned long)sizeIndex];
    [description appendFormat:@"Size: %lu\n", (unsigned long)size];

    for (int i = 0; i < size; i++) {
        [description appendFormat:@"[%d] %@ - %@\n", i, [storage[2*i] description], [storage[2*i + 1] description]];
    }
    
    return description;
}

El orden de las claves/objetos en la enumeración es el mismo que el orden de las claves/objetos en el almacenamiento

El orden de las claves/objetos en la enumeración es el mismo que el orden de las claves/objetos en el almacenamiento.

Creemos un diccionario simple que contenga cuatro valores: Creemos un diccionario simple con cuatro valores:

NSDictionary *dict = @{@1 : @"Value 1",
                       @2 : @"Value 2",
                       @3 : @"Value 3",
                       @4 : @"Value 4"};

NSLog(@"%@", [dict explored_description]);

El resultado de la descripción explorada es: El resultado de la descripción explorada es:

Count: 4
Size index: 2
Size: 7
[0] (null) - (null)
[1] 3 - Value 3
[2] (null) - (null)
[3] 2 - Value 2
[4] (null) - (null)
[5] 1 - Value 1
[6] 4 - Value 4

Con eso en mente, hagamos una enumeración rápida del diccionario: Con esto en mente, hagamos un diccionario de enumeración rápido:

[dict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
    NSLog(@"%@ - %@", key, obj);
}];

Y la salida: y salida:

3 - Value 3
2 - Value 2
1 - Value 1
4 - Value 4

La enumeración parece simplemente recorrer el almacenamiento, ignorando las claves nil y llamando al bloque solo para las ranuras que no están vacías. Este también es el caso de los métodos de enumeración rápida keyEnumerator, allKeys y allValues. Tiene mucho sentido. El NSDictionary no está ordenado, por lo que realmente no importa en qué secuencia se proporcionen las claves y los valores. Usar el diseño interno es la opción más fácil y probablemente la más rápida. La enumeración parece simplemente iterar sobre el almacenamiento, ignorando claves nulas y solo llamando a bloques para espacios no nulos. Este también es el caso de la enumeración rápida, los enumeradores de claves y los métodos allKeys y allValues. Esto tiene mucho sentido. NSDictionary no está ordenado, por lo que el orden de las claves y los valores no importa. Usar un diseño interno es la opción más fácil y rápida.

Si te equivocas, __NSDictionary¡Puedo devolver algo por una clave nula! Si te equivocas, __nsdictionary ¡Puedo devolver algo por una clave nula!

Consideremos un ejemplo. Imaginemos que estamos construyendo un sencillo juego de estrategia en 3D ambientado en el espacio. El universo entero está dividido en sectores cúbicos por los que pueden luchar facciones imaginarias. Se puede hacer referencia a un sector mediante sus índices i, j y k. desperdiciaría memoria almacenando punteros nil. En su lugar, usaremos un almacenamiento disperso en forma de NSDictionary con una clase de clave personalizada que hará que sea muy fácil consultar si hay algo en una ubicación determinada. Consideremos un ejemplo. Digamos que estamos construyendo un juego de estrategia 3D simple. El universo entero está dividido en áreas cúbicas por las que pueden luchar facciones imaginarias. Se puede referenciar un sector por sus índices i, j y k. No deberíamos usar una matriz 3D para almacenar información del sector: el espacio del juego es enorme y está casi vacío, por lo que estaríamos desperdiciando memoria almacenando punteros nulos. En su lugar, usaremos un almacenamiento disperso en forma de NSDictionary, con una clase de clave personalizada que hará que sea muy fácil consultar si hay algo en una ubicación determinada.

Aquí está la interfaz de la clave, una clase BC3DIndex: Esta es la interfaz de clave, una clase BC3DIndex:

@interface BC3DIndex : NSObject <NSCopying>

@property (nonatomic, readonly) NSUInteger i, j, k; // you actually can do that

- (instancetype)initWithI:(NSUInteger)i j:(NSUInteger)j k:(NSUInteger)k;

@end

Y su implementación igualmente trivial: Y su implementación igualmente trivial:

@implementation BC3DIndex

- (instancetype)initWithI:(NSUInteger)i j:(NSUInteger)j k:(NSUInteger)k
{
    self = [super init];
    if (self) {
        _i = i;
        _j = j;
        _k = k;
    }
    return self;
}

- (BOOL)isEqual:(BC3DIndex *)other
{
    return other.i == _i && other.j == _j && other.k == _k;
}

- (NSUInteger)hash
{
    return _i ^ _j ^ _k;
}

- (id)copyWithZone:(NSZone *)zone
{
    return self; // we're immutable so it's OK
}

@end
```Observe cómo estamos siendo buenos ciudadanos de subclasificación: implementamos los métodos `isEqual`: y `hash` y nos aseguramos de que si dos índices 3D son iguales, sus valores hash también lo sean. Se cumplen los requisitos de igualdad de objetos.
Observe cómo estamos siendo un buen ciudadano de subclases: implementamos los métodos isEqual: y hash y nos aseguramos de que si dos índices 3d son iguales, entonces sus hashes también lo son. Se cumple el requisito de igualdad de objetos.

Aquí hay una trivia: ¿qué imprimirá el siguiente código?
Aquí hay una pequeña pregunta: ¿qué imprimirá el siguiente código?

NSDictionary *indexes = @{[[BC3DIndex alloc] initWithI:2 j:8 k:5] : @“A black hole!”, [[BC3DIndex alloc] initWithI:0 j:0 k:0] : @“Asteroids!”, [[BC3DIndex alloc] initWithI:4 j:3 k:4] : @“A planet!”};

NSLog(@“%@”, [indexes objectForKey:nil]);

Debería ser `(null)` ¿verdad? No:
Debería ser (nulo), ¿verdad? No:

Asteroids!

Para investigar esto más a fondo, tomemos la descripción de un diccionario:
Para investigar esto más a fondo, obtengamos una descripción del diccionario:

Count: 3 Size index: 1 Size: 3 [0] <BC3DIndex: 0x17803d340> - A black hole! [1] <BC3DIndex: 0x17803d360> - Asteroids! [2] <BC3DIndex: 0x17803d380> - A planet!

Resulta que `__NSDictionaryI` no verifica si el `key` pasado a `objectForKey:` es `nil` (y yo diría que es una buena decisión de diseño). Llamar al método `hash` en `nil` devuelve `0`, lo que hace que la clase compare la clave en el índice `0` con `nil`. Esto es importante: es la clave almacenada la que ejecuta el método `isEqual:`, no la clave pasada.
El resultado es que __nsdictionari no verifica si la clave pasada a objectForKey: es nula (lo cual creo que es una buena decisión de diseño). Llamar al método hash en nulo devolverá 0, lo que hará que la clase compare la clave en el índice 0 con nulo. Esto es importante: es la clave almacenada la que ejecuta el método isEqual:, no la clave pasada.

La primera comparación falla, ya que el índice `i` indica “¡Un agujero negro!” es `2` mientras que para `nil` es cero. Las claves no son iguales lo que hace que el diccionario siga buscando, pulsando otra clave almacenada: la de “¡Asteroides!”. Esta clave tiene las tres propiedades `i`, `j` y `k` iguales a `0`, que también es lo que `nil` devolverá cuando se le soliciten sus propiedades (mediante la verificación `nil` dentro de `objc_msgSend`).
La primera comparación falló porque indexé "¡Un agujero negro!" que es 2 y nil es 0. Las dos claves no son iguales, lo que hace que el diccionario siga buscando y presione otra clave almacenada: "¡Asteroide!" Esta clave tiene los tres atributos i, j y k que son iguales a 0, que también es el valor que devuelve nil al solicitar sus atributos (a través de la verificación nil en objc_msgSend).

Éste es el meollo del problema. La implementación `isEqual:` de `BC3DIndex` puede, bajo algunas condiciones, devolver `YES` para la comparación con `nil`. Como puedes ver, este es un comportamiento muy peligroso que puede estropear las cosas fácilmente. Asegúrese siempre de que su objeto no sea igual a `nil`.
Éste es el quid de la cuestión. isEqual: bajo ciertas condiciones, las implementaciones de BC3DIndex pueden devolver SÍ para comparaciones nulas. Como puede ver, este es un comportamiento muy peligroso y puede estropear las cosas fácilmente. Asegúrese siempre de que el objeto no sea igual a cero.

#### Una clase de clave auxiliar Clase de clave auxiliar

Para las próximas dos pruebas, crearemos una clase de clave especial que tendrá un valor hash configurable e imprimirá elementos en la consola al ejecutar los métodos `hash` y `isEqual:`.
En las siguientes dos pruebas, crearemos una clase de clave especial que tendrá un valor hash configurable e imprimiremos el contenido en la consola cuando se ejecuten los métodos hash e isEqual:.

Aquí está la interfaz:
Esta es la interfaz:

@interface BCNastyKey : NSObject <NSCopying>

@property (nonatomic, readonly) NSUInteger hashValue;

• (instancetype)keyWithHashValue:(NSUInteger)hashValue;

@end

Y la implementación:

@implementation BCNastyKey

• (instancetype)keyWithHashValue:(NSUInteger)hashValue { return [[BCNastyKey alloc] initWithHashValue:hashValue]; }

• (instancetype)initWithHashValue:(NSUInteger)hashValue { self = [super init]; if (self) { _hashValue = hashValue; } return self; }

• (id)copyWithZone:(NSZone *)zone { return self; }

• (NSUInteger)hash { NSLog(@“Key %@ is asked for its hash”, [self description]);

  return _hashValue; }

• (BOOL)isEqual:(BCNastyKey *)object { NSLog(@“Key %@ equality test with %@: %@”, [self description], [object description], object == self ? @“YES” : @“NO”);

  return object == self; }

• (NSString *)description { return [NSString stringWithFormat:@“(&:%p #:%lu)”, self, (unsigned long)_hashValue]; }

@end

Esta clave es horrible: solo somos iguales a nosotros mismos, pero devolvemos un hash arbitrario. Observe que esto no rompe el contrato de igualdad.
Esta clave es mala: solo nos igualamos a nosotros mismos, pero devolvemos un hash arbitrario. Tenga en cuenta que esto no viola el contrato de igualdad.

#### no es necesario llamar a isEqual para que coincida con la clave

Creemos una clave y un diccionario:
Creemos una clave y un diccionario:

BCNastyKey *key = [BCNastyKey keyWithHashValue:3]; NSDictionary *dict = @{key : @“Hello there!”};

La siguiente convocatoria:
Los siguientes números de teléfono:

[dict objectForKey:key];

Imprime esto en la consola:
Imprimir en la consola:

Key (&:0x17800e240 #:3) is asked for its hash

Como puede ver, no se ha llamado al método `isEqual:`. ¡Esto es genial! Dado que la gran mayoría de claves que existen son literales `NSString`, comparten la misma dirección en toda la aplicación. Incluso si la clave es una cadena literal muy larga, el `__NSDictionaryI` no ejecutará el método `isEqual:`, que potencialmente consume mucho tiempo, a menos que sea absolutamente necesario. Y dado que las arquitecturas de 64 bits introdujeron punteros etiquetados, algunas instancias de `NSNumber`, `NSDate` y, aparentemente, `NSIndexPath` también se benefician de esta optimización.
Como puede ver, el método isEqual: aún no ha sido llamado. ¡Esto es genial! Dado que la gran mayoría de las claves son literales NSString, comparten la misma dirección en toda la aplicación. Incluso si la clave es una cadena literal larga, __NSDictionaryI no ejecutará el método isEqual: que puede consumir mucho tiempo a menos que sea absolutamente necesario. Dado que las arquitecturas de 64 bits introdujeron punteros etiquetados, algunas instancias de NSNumber, NSDate y NSIndexPath aparentemente también se beneficiaron de esta optimización.

#### El rendimiento en el peor de los casos es lineal El rendimiento en el peor de los casos es lineal

Creemos un caso de prueba muy simple:
Creemos un caso de prueba muy simple:

BCNastyKey *targetKey = [BCNastyKey keyWithHashValue:36];

NSDictionary *b = @{[BCNastyKey keyWithHashValue:1] : @1, [BCNastyKey keyWithHashValue:8] : @2, [BCNastyKey keyWithHashValue:15] : @3, [BCNastyKey keyWithHashValue:22] : @4, [BCNastyKey keyWithHashValue:29] : @5, targetKey : @6 };

Una sola línea asesina:
Una simple carta de triunfo:

NSLog(@“Result: %@”, [[b objectForKey:targetKey] description]);

Revela el desastre:
Desastre revelado:

Key (&:0x170017640 #:36) is asked for its hash Key (&:0x170017670 #:1) equality test with (&:0x170017640 #:36): NO Key (&:0x170017660 #:8) equality test with (&:0x170017640 #:36): NO Key (&:0x170017680 #:15) equality test with (&:0x170017640 #:36): NO Key (&:0x1700176e0 #:22) equality test with (&:0x170017640 #:36): NO Key (&:0x170017760 #:29) equality test with (&:0x170017640 #:36): NO Result: 6

Este es un caso extremadamente patológico: cada clave del diccionario ha sido sometida a pruebas de igualdad. Aunque cada hash era diferente, colisionaba con todas las demás claves, porque los hash de las claves eran congruentes en módulo 7, que resultó ser el tamaño de almacenamiento del diccionario.
Este es un caso extremadamente patológico: cada clave del diccionario se prueba para determinar la igualdad de Ben. Aunque cada hash es diferente, todavía choca con otras claves porque el hash de la clave es módulo 7, que es el tamaño de almacenamiento del diccionario.Como se mencionó anteriormente, observe que falta la última prueba `isEqual:`. El `__NSDictionaryI` simplemente comparó los punteros y descubrió que debía ser la misma clave.
Como se mencionó anteriormente, observe que falta el último isEqual: test. __nsdictionari simplemente compara los punteros y descubre que deben ser la misma clave.

¿Deberías preocuparte por esta búsqueda de tiempo lineal? En absoluto. No me gusta mucho el análisis probabilístico de la distribución de hash, pero tendrías que tener mucha suerte para que todos tus hashes sean módulo congruente con el tamaño del diccionario. Siempre ocurrirán algunas colisiones aquí y allá, esta es la naturaleza de las tablas hash, pero probablemente nunca se encontrará con el problema del tiempo lineal. Es decir, a menos que arruines tu función `hash`.
¿Debería importarle esta adquisición de tiempo lineal? En absoluto. No soy un gran admirador del análisis probabilístico de distribuciones hash, pero debes tener mucha suerte de que todos tus hashes sean un módulo del tamaño del diccionario. Siempre habrá algunas colisiones aquí y allá, esa es la naturaleza de las tablas hash, pero probablemente nunca te encontrarás con un problema de tiempo lineal. A menos que hayas estropeado la función hash.

### Palabras finalesPalabras finales

Me fascina lo simple que resultó ser el `__NSDictionaryI`. No hace falta decir que la clase ciertamente cumple su propósito y no hay necesidad de complicar demasiado las cosas. Para mí, el aspecto más hermoso de la implementación es el diseño clave-objeto-clave-objeto. Ésta es una idea brillante.
Me intrigó lo simple que resultó ser este diccionario. No hace falta decir que esta clase ciertamente cumple su propósito y no hay necesidad de complicar demasiado las cosas. Para mí, el aspecto más hermoso de esta implementación es el diseño clave-objeto-clave-objeto. Ésta es una buena idea.

Si tuvieras que seguir un consejo de este artículo, estaría atento a tus métodos `hash` y `isEqual:`. Por supuesto, rara vez se escriben clases de claves personalizadas para usar en un diccionario, pero esas reglas también se aplican a `NSSet`.
Si sigue un consejo de este artículo, le recomiendo que preste atención a los métodos hash e isEqual:. Por supuesto, pocas personas escriben clases de claves personalizadas para usar en diccionarios, pero estas reglas también se aplican a NSSets.

Soy consciente de que en algún momento `NSDictionary` cambiará y mis hallazgos quedarán obsoletos. Internalizar los detalles de la implementación actual puede convertirse en una carga en el futuro, cuando los supuestos memorizados ya no sean aplicables. Sin embargo, aquí y ahora es muy divertido ver cómo funcionan las cosas y espero que compartas mi entusiasmo.
Sé que en algún momento el NSDictionary cambiará y mis hallazgos quedarán obsoletos. Internalizar los detalles de la implementación actual puede convertirse en una carga futura cuando los supuestos recordados ya no sean aplicables. Sin embargo, aquí y ahora, es muy divertido ver cómo funcionan las cosas y espero que puedan compartir mi entusiasmo.



Texto original: https://ciechanow.ski/exposing-nsdictionary/