（转载）自我管理数据缓冲区内存

hobby!

作者：Xiaoming Zhang
C 程序设计语言定义了两个标准的内存管理函数：malloc() 和 free()。C 程序员经常使用那些函数在运行时分配缓冲区，以便在函数之间传递数据。然而在许多场合下，您无法预先确定缓冲区所需的实际大小，这对于构造复杂的 C 程序来说，可能会导致几个根本性的问题。在本文中，Xiaoming Zhang 倡导一种自我管理的抽象数据缓冲区。他概括地给出了抽象缓冲区的伪 C 代码实现，并详细介绍了采用这种机制的优点。
软件的规模和复杂性随时都在增长，从根本上影响了应用程序的体系结构。在许多场合下，将所有功能编码进软件的单个部分中是不切实际的。让独立的软件部分相互交互，比如以插件的形式，这样做的重要性正在变得越来越明显。要相对容易地实现这种交互，甚至是在不同厂商编写的软件部分之间，软件需要有定义良好的接口。使用诸如 C 这样的传统程序设计语言来编写满足这种需要的软件可能是一个挑战。

考虑到这种挑战，本文将研究 C 程序设计语言中的数据缓冲区接口，同时着眼于如何改进当前实践。尽管内存管理看起来可能无足轻重，但是恰当设计的接口能够产生高效、简单和可移植的代码 —— 这其中每个特性都需要进行内存管理才能实现。因而，下一节将概略介绍程序员在采用传统数据缓冲区管理方案时所面对的各种问题。后面跟着要介绍的是抽象数据缓冲区方案，并通过伪代码实现来进行说明，这种方案解决了许多问题；最后要介绍的是一些代码片断，用以演示该解决方案的好处。

传统实践和它们带来的问题
C 程序员经常使用动态分配的缓冲区（通过调用 malloc()/free()函数）在函数之间传递数据。尽管该方法提供了灵活性，但它也带来了一些性能影响。首先，它要求在需要缓冲区块的任何地方进行额外的管理工作（分配和释放内存块）。如果分配和释放不能在相同的代码位置进行，那么确保在某个内存块不再需要时，释放一次（且仅释放一次）该内存块是很重要的；否则就可能导致内存泄露或代码崩溃。其次，必须预先确定缓冲区的大小才能分配该内存块。然而，您也许会发现，确定数据大小并不总是那么容易。开发人员经常采用最大数据尺寸的保守估计，而这样可能导致严重的内存资源浪费。

为避免由于多次释放而导致的可能的内存泄露和代码崩溃，好的编程实践要求您明确地预定义负责分配和释放缓冲区内存的程序部分。然而在实践中，定义职责会导致其他困难。在传统方案下，由于在创建缓冲区时必须指定大小，因此 数据提供者（它可能知道它所提供的数据的大小）是用来执行缓冲区分配操作的最佳搭档。另一方面，用于释放的最佳搭档可能是 数据使用者，因为它知道何时不再需要该数据。通常情况下，数据提供者和数据使用者是不相同的。

当数据提供者和数据使用者来自不同的软件提供商时，进行交互的各方可能采用不同的底层内存管理机制。例如，有些软件提供商可能选择自我管理的堆空间，而其他软件提供商则依赖底层操作系统（OS）来获得这样的功能。此外，不同的操作系统可能以不同的方式实现内存管理。例如，PalmOS 提供两种不同的内存资源：基于堆和基于数据库。一般来讲，不同的内存管理机制具有各自的优点和缺点，因此您可能不希望预先假定某种特定的机制。不同的首选项甚至可能导致相互冲突的代码编写习惯。

解决这个问题的三种方法如下：

交互方之一定义用于数据交换的底层内存分配机制。另一方总是使用已公布的接口来分配或释放缓冲区，从而避免潜在的不一致。这种模型需要双方都坚持一个可能与软件基本功能无关的编程约定，而且在一般情况下，这个编程约定可能使代码更加不可重用。


驱动数据交换的那一方将负责管理操作 —— 当该方充当数据提供者时，这是一个相对适当的方案。 然而，当该方充当数据使用者时，事情就变得棘手了。 为避免去发现数据大小，数据使用者可以分配一个任意大小的缓冲区。如果该数据缓冲区没有足够大，就必须对数据提供者发出多次调用。因此这种方法需要围绕该交互调用编写额外的循环代码，以备多次调用之需。


对于第三种选择，数据使用者将对管理操作负责。然而在这种情况下，如果另一方是数据提供者，数据使用者必须预先发出一次调用以发现缓冲区大小 —— 从而给另一方施加了更多的负担，即编写逻辑代码来提供关于缓冲区大小的信息，而这可能需要执行耗时的算法。而且，这种解决办法还可能引入严重的效率问题：假设函数 a() 从函数 b() 获得数据，后者反过来又在执行期间从函数 c() 获得数据。假设发现缓冲区大小和提供实际的数据都需要执行相同的算法。
为了从 b() 获得数据，a() 必须发出两次调用：一次用于确定缓冲区大小，另一次用于获得实际数据。对于向 a() 发出的每次调用，b() 都必须对 c() 发出两次调用。因此，当这个操作结束时，c() 中的算法代码可能已经执行了四次。原则上，该代码应该仅执行一次。

显而易见地，这三种解决办法全都存在局限性，因此传统缓冲区内存管理方法并不是适合编写大规模交互软件代码的机制。

除了上述困难之外，安全性也证明是传统方法存在的问题：传统缓冲区管理方案无法容易地防止恶意用户刻意改写数据缓冲区，从而导致程序异常。考虑到所有这一切，设计一个适当的数据缓冲区接口就势在必行！

解决方案是什么？
在上一节中，您看到了传统缓冲区方案如何会产生多种问题。与此相反，当您创建一个抽象数据缓冲区时，解决方案就变得简单了。

从概念上讲，数据缓冲区在传统方案下是由两个操作创建的：数据缓冲区实体的创建和实际内存的分配。然而事实上，在实际数据变得可用之前，您不需要分配实际的内存 —— 即可以将两个操作分离开来。

最初可以使用内存块的一个空链表来创建一个抽象缓冲区。抽象数据缓冲区仅在实际数据变得可用时才分配内存。释放内存也变成了抽象数据缓冲的责任。考虑到所有这些，集中内存管理和数据复制操作就会带来以下优点：

各方都能通过调用预定义的 API 函数来构造和/或销毁数据缓冲区。
内存使用将保持接近最优状态，因为缓冲区内存仅在必要时才分配，并且会尽快释放，从而最小化内存泄露。
任何一方都不需要知道底层的内存管理方案，使得软件高度可移植，同时保证了交互双方之间的兼容性。
由于没有哪一方需要管理内存，确定缓冲区的大小就变得不必要了（因而也不可能存在前面指出的多次执行问题）。
事实证明缓冲区溢出也不可能会发生，因为仅当存在额外数据空间时才会复制数据。
一种简单的实现
为了表示一个抽象数据缓冲区，需要声明两个结构化的数据类型：

清单 1. 声明两个结构化的数据类型来表示一个抽象数据缓冲区

typedef struct BufferBlockHeader_st BufferBlockHeader;

struct BufferBlockHeader_st {
   BufferBlockHeader * pNextBlock;
};

struct Buffer_st {
   long  int             totalLength;
   BufferBlockHeader *   pFirstBlock;
   short int             startPoint;
   BufferBlockHeader *   pLastBlock;
   short int             endPoint;
};

typedef struct Buffer_st Buffer;



Buffer 包含关于已创建的抽象缓冲区的信息，它还管理内存块的一个链表：

totalLoength 记录当前存储在缓冲区中的字节数。
pFirstBlock 指向该链表中的第一个内存块。
startPoint 记录第一个内存块中第一个字节的偏移位置。
pLostBlock 指向该链表的最后一个内存块。
endPoint 记录最后一个内存块中第一个空闲字节的偏移位置。
您可以向 Buffer 引入一个附加参数，用以指定每个内存块的大小，并且可以在抽象缓冲区的初始化期间，将该参数设置为一个可取的值。这里假设使用默认块大小。

如果分配了的话，BufferBlockHeader 结构中的 pNextBlock 总是指向该链表中的下一个内存块。每个内存块在分配时都包含一个 BufferBlockHeader 头，后面跟着一个用于存储实际数据的缓冲区块。

图 1 描述了一个存储了一些数据的抽象缓冲区。

图 1. 抽象缓冲区的数据结构


M 表示 Buffer 的大小（它通常为 20 字节），B 表示所选择的内存块大小。内存开销大约为 (M+B) 个字节（每个内存块开头的指针忽略不计）。 (M+B)中的 B 平均起来仅有所使用的第一和最后一个内存块的一半。这个开销几乎保持不变。

在能够缓冲数据之前，必须通过调用下面的 newBuffer() 函数来显式地创建抽象缓冲区：

清单 2 使用 newBuffer() 函数创建抽象缓冲区

Buffer * newBuffer() {
   allocate a Buffer structure;
   initialize the structure;
}



在清单 2 中，该函数分配了包含一个 Buffer 的内存块，并初始化它的条目以指明它是一个空抽象缓冲区。

相应地，必须在使用抽象缓冲区之后通过调用下面的 freeBuffer() 函数来销毁它：

清单 3 使用 freeBuffer() 函数来销毁抽象缓冲区

void freeBuffer(Buffer * pBuffer    /* pointer to the buffer to be freed */
               ) {
   while (there is more memory block in the linked list) {
      free the next memory block;
   }
   free the Buffer structure;
}



清单 3 中的函数释放链表中的所有内存块，然后释放由 newBuffer() 分配的 Buffer。

要逐步向抽象缓冲区追加数据段，可使用以下函数：

清单 4. 逐步向抽象缓冲区追加数据段

long int appendData(Buffer * pBuffer,    /* pointer to the abstract buffer */
             byte *   pInput,    /* pointer to the data source */
             long int offset,    /* offset of the input data */
             long int dataLength    /* number of bytes of the input data */
               ) {
   while (there is more input data) {
      fill the current memory block;
      if (there is more input data) {
         allocate a new memory block and add it into the linked list;
      }
   }      
}



清单 4 中的函数把存储在 pInput[offset..offset+dataLength] 中的字节复制到 pBuffer 所指向的抽象缓冲区中，并在必要时在链表中插入新的内存块，然后返回成功复制到抽象缓冲区中的字节数目。

采用类似的方式，您可以使用以下函数，逐段地从抽象缓冲区读取数据段：

清单 5. 从抽象缓冲区读取数据段

long int readData(Buffer * pBuffer,    /* pointer to the abstract buffer */
           byte *   pOutput,    /* pointer to the output byte array */
           long int offset,    /* offset of the output byte array */
           long int arrayLength    /* size of available output byte array */
             ) {
   while (there is something more to read and there is room for output) {
      read from the first memory block;
      if (the first memory block is empty) {
         delete the first memory block from the linked list and free its memory;
      }
   }
}



在清单 5 中，该函数销毁性地从 pBuffer 所指向的抽象缓冲区最多读取 arrayLength 个前导字节，并在内存块变为空时从链表中删除它们，然后返回成功读取的字节数目。

如果需要，您可以实现一个类似 readData() 的函数来允许非销毁性的读取。

实现一个函数来返回当前存储在抽象缓冲区中的字节数目，这样可能会带来好处。

清单 6. 返回抽象缓冲区中的字节数目

long int bytesAvailable(Buffer * pBuffer  /* pointer to the abstract buffer */
                       ) {
   return totalLength;
}



使用抽象缓冲区的优点
您在前面看到了与传统缓冲区方案相关联的几个困难方面。作为一种替代方法，通过集中内存管理和数据复制操作，本文建议的抽象缓冲区立即消除了发生不一致的内存管理和缓冲区溢出的可能性。它还使得代码编写更简单，并避免了前面指出的可能的多次执行问题。为了更好地理解这个解决方案，让我们考察一个使用伪代码的例子，该例子首先使用传统方法，然后使用集中的解决方案。

比固定大小的缓冲区方法更简单的代码编写
假设函数 a() 从函数 b() 获取输入数据，但是不知道函数 b() 的大小。您可以让 a() 分配一个固定大小的缓冲区，然后反复调用 b()，直至 b() 已指出到达了输入数据的结尾，从而避免查询输入数据的大小。

清单 7. 分配固定大小的缓冲区并调用输入数据

int b(byte *buf, int bufSize) {
   fill buf;
   return size of output;
}

void a() {

   byte * buf = malloc(BUFFER_SIZE);
   int size;

   if (NULL != buf) {
      while (there is more data from b()) {
         size = b(buf, BUFFER_SIZE);
         process data in buf;
      }
      free(buf);
   }

}



通过使用抽象缓冲区，代码可简化为：

清单 8. 为抽象缓冲区调用输入数据

void b(Buffer *buf) {
   fill buf;
}

void a() {

   Buffer * buf = newBuffer();
   if (NULL != buf) {
      b(buf);
      process data in buf;
      freeBuffer(buf);
   }

}



无多次执行的方法和发现数据大小的方法之间的比较
同样，假设函数 a() 从函数 b() 获取输入数据，但是不知道 b() 的大小。为了给 b() 分配足够大的缓冲区，a() 必须对 b() 发出高级发现调用（假设只有 b() 知道大小）。a() 将类似如下：

清单 9. 发出高级发现调用

int b(byte *buf, int bufSize) {
   if (NULL != buf) {
      fill buf;
   }
   return size of output;
}

void a() {

   int size = b(NULL, 0);
   byte * buf = malloc(size);
   if (NULL != buf) {
      b(buf, size);
      process data in buf;
      free(buf);
   }
}



注意 a() 调用了 b() 两次。

通过使用抽象缓冲区，您可以将代码编写为：

清单 10. 对抽象缓冲区发出单次发现调用

void b(Buffer *buf) {
   fill buf;
}

void a() {

   Buffer * buf = newBuffer();
   if (NULL != buf) {
      b(buf);
      process data in buf;
      freeBuffer(buf);
   }

}



它仅调用 b() 一次。

结束语
本文研究了当两个 C 函数使用传统数据缓冲区管理方案进行交互时所产生的问题。在编写大规模交互软件代码时，这样的问题可能会变成主要问题。作为一种替代方案，自我管理的抽象数据缓冲区能够解决那些问题。 对于普通 C 程序员来说，实现这种建议的抽象数据缓冲区应该是一项相对容易的任务。

为了从这种解决方案中获益，您必须清楚地定义具体的抽象数据缓冲区接口。采用这样一个接口将简化以后的代码开发。然而，如果要将现有代码移植为使用这样的接口，您必须保持谨慎，并在权衡成本/收益比的同时进行逐个案例的分析。